748
правок
Изменения
→Доказательство корректности
==Доказательство корректности==
{{Утверждение
|statement=Алгоритм строит корректное расписание.
|proof=Если мы успеваем выполнить очередную работу, то, очевидно, от ее добавления, расписание не может стать некорректным. В противном случае мы пытаемся заменить одну работу из множества <tex> S </tex> на текущую. Но это так же не может сделать наше расписание некорректным. Это следует из того, что мы рассматриваем работы в порядке неуменьшениях их дедлайнов. Пусть мы заменяем работу <tex> k </tex> на работу <tex> i </tex>. Но <tex> d_{k} \leqslant d_{i} </tex>, следовательно, если мы успевали выполнить работу <tex> k </tex>, то успеем выполнить и работу <tex> i </tex>.
}}
==Время работы==
