6.3 Задачи и дедлайны

Рассмотрим следующую задачу. Нам дано n задач; для каждой известны длительность выполнения и дедлайн. Нужно выбрать порядок выполнения задач. За каждую задачу начисляется d - x очков, где d — её дедлайн, а x — момент времени, когда мы закончили эту задачу. Требуется получить как можно больший суммарный результат.

Например, пусть заданы такие задачи:

Задача	Длительность	Дедлайн
A	5	3
B	2	6
C	1	8
D	4	7

Один из оптимальных порядков выполнения:

C → B → D → A

Временная шкала завершений:

• после C: время 1
• после B: время 3
• после D: время 7
• после A: время 12

Тогда очки будут такими:

• C: 8 - 1 = 7
• B: 6 - 3 = 3
• D: 7 - 7 = 0
• A: 3 - 12 = -9

Итоговая сумма равна 7 + 3 + 0 - 9 = 1.

Жадная идея

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

Правильная жадная стратегия такая:

выполнять задачи в порядке возрастания их длительности.

Почему это верно

Предположим, что в некотором расписании подряд стоят две задачи:

• сначала задача X длительности a,
• потом задача Y длительности b,

где a > b.

То есть более длинная задача стоит раньше более короткой.

Пусть обе задачи начинаются после некоторого уже прошедшего времени t.

Тогда:

• X завершится в момент t + a,
• Y завершится в момент t + a + b.

Если поменять их местами, то:

• Y завершится в момент t + b,
• X завершится в момент t + b + a.

Посмотрим, как изменится сумма очков.

До перестановки вклад этих двух задач равен:

(d_X - (t + a)) + (d_Y - (t + a + b))

После перестановки:

(d_Y - (t + b)) + (d_X - (t + b + a))

Разница между новой и старой суммой оказывается равной:

a - b

А так как a > b, эта величина положительна. Значит, после перестановки суммарный результат увеличится.

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

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

Итого

Чтобы получить максимальную сумму очков:

1. отсортируем все задачи по длительности;
2. выполним их в этом порядке.

Именно такой жадный алгоритм всегда даёт оптимальный ответ.

Что важно запомнить

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

Это хороший пример жадного алгоритма, где правильная стратегия выглядит немного неожиданно.