Изменения
→Доказательство корректности алгоритма
|statement=
Пусть <tex> \pi -</tex> любая оптимальная последовательность работ для данных дедлайнов <tex>d_1, d_2,\ldots, d_n</tex>, <tex>C_j -</tex> время завершения выполнения <tex>j</tex>-ой работы.
Рассмотрим <tex>d'_j</tex> такие, что <tex>\min\{d_j, C_j\} \leqslant d'_j \leqslant \max\{d_j, C_j\}. </tex>Тогда любая оптимальная последовательность работ для <tex> d_j</tex> будет оптимальна и для <tex>d'_j</tex>.
|proof=
Рассмотрим последовательность <tex>\pi'</tex> оптимальную для <tex>d'_j</tex>. Тогда <tex>C'_j - </tex> время завершения работы <tex>j</tex> в данной последовательности. <br>
<tex>T( \pi) = T′(\pi) + \sum\limits_{i=1}^n A_j</tex>, <br>
<tex>T( \pi′) = T ′(\pi′) + \sum\limits_{i=1}^n B_j</tex>, <br>
