Интервальное планирование

Рассмотрим очень простую задачу планирования. Имеется некий ресурс — аудитория, суперкомпьютер, электронный микроскоп и т. д.; множество людей обращается с заявками на использование ресурса в течение периода времени.

Заявка имеет вид: «Можно ли зарезервировать ресурс, начиная с времени s и до времени f?» Будем считать, что ресурс в любой момент времени может использоваться только одним человеком. Планировщик выбирает подмножество заявок, отклоняя все остальные, чтобы принятые заявки не перекрывались по времени. Целью планирования является максимизация количества принятых заявок.

Более формальная постановка: имеется n заявок с номерами 1, …, n; в каждой заявке i указывается начальное время si и конечное время fi. Естественно, si < fi для всех i. Две заявки i и j называются совместимыми, если запрашиваемые интервалы не перекрываются, то есть заявка i приходится либо на более ранний интервал времени, чем у j ( fi ≤ sj), либо на более поздний интервал времени, чем у j ( fj ≤ si).

В более общем смысле подмножество A заявок называется совместимым, если все пары запросов i, j Ѯ A, i ≠ j являются совместимыми. Целью алгоритма является выбор совместимого подмножества заявок максимально возможного размера.

Вскоре мы увидим, что эта задача может быть решена с применением очень естественного алгоритма, который упорядочивает множество заявок по некоторой эвристике, а затем «жадно» обрабатывает их за один проход, выбирая совместимое подмножество максимально возможного размера. Это типично для категории «жадных» (greedy) алгоритмов, которые мы будем рассматривать для различных задач, — «недальновидных» правил, которые обрабатывают входные данные по одному элементу без сколько-нибудь очевидных опережающих проверок.

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