Встреча максимум гостей (интервал времени) в k попыток

Question

Идет вечеринка, указывается интервал времени для каждого гостя в вечеринке.Я могу пойти в комнату для вечеринок k раз.Теперь я должен выбрать k временных инстансов, чтобы встретить максимальное количество гостей

n - нет.гостей к - нет.попыток

Пример: для n = 5 & k = 2

с интервалом в 5 гостей [1,3] [4,8] [1,5] [6,8] [4,8] Во время = 1 я могу встретить 1-го и 3-го гостя, а во время = 6 я могу встретить 2-го, 4-го и 5-го гостя. Поэтому я могу встретить максимум 5 гостей в 2-х попытках.Мои неудачные подходы:

1. Использовал дерево интервалов, чтобы найти точки максимального перекрытия, удалил интервалы в этой точке и сделал то же самое во второй раз.Это терпит неудачу, потому что это дает только точку максимального гостя, как я получил время = 4 в этом примере.Что является плохим выбором, потому что тогда я могу встретить только 4 гостей.(3 во время = 4 и 1 во время = 1 или время = 6) Так что я думаю, что это динамическое программирование, и теперь я поражен.Дайте или предложите мне алгоритм или решение.Заранее спасибо

Answer 1

Составьте список моментов времени, когда кто-нибудь входит (или аналогичных моментов, когда кто-то покидает комнату, как советовал @Ajris).Здесь времена равны 1,4,6

Построить график (он на данный момент двунаправленный), левая часть содержит гостей, правая часть содержит временные точки.Для каждого гостя сделайте ребра в момент времени, когда он был в комнате.Вот ребра:

 g1: t1
 g2: t4, t6
 g3  t1, t4
 g4: t6
 g5: t4 ,t6

Теперь добавьте вспомогательную вершину S 'слева к гостям и добавьте ребра с единичной вместимостью для всех гостей (график не более двудольный, просто направленный).Добавьте еще одну вершину S (источник) слева к S 'и сделайте ребро SS' с емкостью K

Также добавьте целевую вершину T справа от времени и добавьте ребра из каждой временной точки (с емкостью K).

Теперь решите проблему максимального целочисленного потока для пары источник-приемник ST с помощью любого доступного алгоритма

Answer 2

Ну, я бы предложил перейти к динамическому программированию. Вы можете легко проверить, что «лучшее время» для входа в комнату для вечеринок - это время, когда чье-то время истекло. В вашем примере это будет 3,5 и 8. Тогда вы хотите рассчитать наилучший из возможных сценариев получения 2 из него (я все еще решаю его на вашем примере, так как думаю, что это будет лучшим объяснением). И здесь вы можете вычислить, что было бы, если бы вы взяли 3, затем 5, затем 8 и рассчитали для них ту же рекурсию. Вы можете сохранить заданное время, чтобы избежать дублирования, и после того, как вы закончили свои k-шаги, просто проверьте его размер, и самое большое решение - это решение.