Оптимизация: минимизировать количество встреч

#algorithm #optimization

#алгоритм #оптимизация

Вопрос:

Это вопрос интервью

Есть авиакомпания, которая хочет предоставлять новые обновления всем своим бортпроводникам посредством встреч. У каждого i-го бортпроводника есть рабочее время от времени начала i (si) до времени окончания i (ei) . Разработайте алгоритм, который минимизирует количество совещаний, которые должна проводить компания.

Мой подход заключается в том, чтобы выбрать бортпроводника, у которого наименьшее время окончания. Затем удалите всех тех участников, время начала которых <= это время окончания (потому что они уже знают обновления с собрания). Продолжайте, пока не останется больше стюардессы для выбора. Авиакомпания должна проводить встречи во время окончания тех обслуживающий персонал, которых я выбираю.

Правильный ли это подход? Если да, то как доказать его правильность.

Я думаю, что сложность равна O (n log n), поскольку я сначала отсортирую список в порядке возрастания времени окончания и пройдусь по списку один раз.

1. Пожалуйста, будьте немного конкретнее в проблеме; таким образом, любое собрание достигает всех участников, которые работают во время проведения собрания? Однако ваша оценка сложности времени выполнения верна для алгоритма, который вы описываете.

2. Если вместо этого вы выберете бортпроводника с самым ранним временем начала и проведете встречу заранее, вы можете обслуживать их всех одной встречей.

3. @LasseV.Karlsen: пожалуйста, уточните. вы только что изменили направление сканирования? это тоже сработало бы, но не так, как вы описали.

4. Я думаю, я неправильно понял смысл «рабочего времени», поскольку они являются бортпроводниками, разве они не находятся в полете в рабочее время? Я предположил, что встречи нужно будет проводить вне рейсов.

Ответ №1:

Насколько я понимаю, описанный алгоритм дает оптимальное решение по следующему аргументу. Исправьте экземпляр и его оптимальное решение; исправьте самое раннее время окончания t рабочего периода; если собрание запланировано на t-1 , все рабочие периоды, начинающиеся раньше, чем t , могут обслуживаться этим собранием, поэтому любое оптимальное решение, использующее более одного собрания до t , может быть улучшено. С другой стороны, должна быть хотя бы одна встреча до времени t-1 , поскольку в противном случае некоторые рабочие периоды не могли быть обслужены.

После удаления отработанного рабочего времени мы получаем меньший экземпляр той же проблемы. Используя приведенный выше аргумент итеративно, получается минимальное количество встреч.