Изменение графика работы

Question

Я пытаюсь решить вариацию задачи планирования интервалов: учитывая набор из n заданий, каждое из которых требует 1 единицу обработки до конечной sh, и у каждого задания есть интервал доступности (время начала и время окончания между которыми оно может быть выполнено), для которого оно доступно, найдите максимальное количество заданий, которое можно запланировать.

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

while jobs are not empty:
    remove jobs that are not available
    find the job with earliest end_availability_time
    execute the job

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

Существует ли оптимальный способ решения этой проблемы?

Answer 1

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

Один из возможных алгоритмов для решения этой проблемы - Венгерский алгоритм , или вы можете закодировать ее как задачу максимальный поток и решить ее с помощью алгоритма Форда-Фулкерсона .

Редактировать Думая о Более того, ваше решение также является оптимальным. Вот набросок доказательства: пусть A - оптимальное решение, найденное жадным алгоритмом, а B - другое оптимальное решение. Рассмотрим задание j, которое запланировано в B, но не в A. Это означает, что жадный алгоритм удалил j из списка доступных заданий, что может произойти, только если он запланировал другое задание на каждый интервал времени в интервале доступности j. Тогда одно из этих заданий не может быть в B, потому что оно будет запланировано в то же время j. Таким образом, это означает, что A и B имеют одинаковое количество заданий.

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