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