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