Изменения

}}

== Описание алгоритма ==

Оптимальное расписание для этой задачи будем задавать множеством работ <tex>S</tex>, которые будут выполнены в срок. Работы, которые не войдут в <tex>S</tex>, то есть завершатся с опозданием, могут быть выполнены в конце в любом порядке.<br>

Чтобы построить множество <tex>S</tex>, будем добавлять работы в порядке неуменьшения их времен окончания, и как только некоторая работа <tex>j</tex> опаздывает, удалим из <tex>S</tex> работу с минимальным значением <tex>w_i</tex> и поставим <tex>j</tex> на ее место.<br>

Пусть есть работы <tex>1 \ldots n</tex> с временами окончания <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>. Будем называть ''простоем '' временной интервал, в который на машине ничего не обрабатывается. Тогда следующий алгоритм вычислит оптимальное множество <tex>S</tex>.

добавить <tex>i</tex> в <tex>S</tex> и поставить <tex>i</tex> на место самого раннего простоя

Таким образом, работы, не попавшие в <tex>S</tex>, будут иметь минимальное значение <tex>w_i</tex>.

== Доказательство корректности ==