Изменения
→Доказательство
|statement=Расписание, построенное данным алгоритмом, оптимально.
|proof=Пусть <tex> l</tex> — максимальное опоздание оптимального расписания. Тогда
<tex>\overset{n}{max\undersetlimits_{i=1}{\max}..n}L(i) = \overset{n}{max\undersetlimits_{i=1}{\max}..n}(C_i - d_i) \leqslant l</tex> эквивалентно<tex>\overset{n}{max\undersetlimits_{i=1}{\max}..n}(C_i - (d_i+l)) \leqslant 0</tex>.
По первой лемме, данный алгоритм применительно к задаче с дедлайнами <tex> d_i + l</tex> дает оптимальное расписание для исходной задаче. Кроме того, это расписание совпадает с расписанием, которое мы получим, применив данный алгоритм к исходной задаче.
