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

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

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

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

Пример задачи интервального планирования представлен на рис. 1.4. На диа- грамме представлено одно совместимое множество размера 4, и оно является самым большим совместимым множеством.

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

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