Изменения
→Алгоритм
<tex>S = \varnothing</tex>
<tex>time = 0</tex>
'''for''' i = 1 '''to''' n '''do'''
<tex>d_i = \min\{d_i, n\}</tex>
'''for''' i = 1 '''to''' n '''do'''
'''if''' <tex>time < d_i</tex>
<tex>time</tex> <code>+=</code> <tex>1</tex>
Cортировку работ по неубыванию дедлайнов осуществляем с помощью сортировки подсчетом за <tex>O(n)</tex>, а значит и весь алгоритм будет работать за <tex>O(n)</tex>. Во время сортировки стоит учитывать, что дедлайны могут значительно превосходить количество задач. В таком случае необходимо предварительно пересчитать дедлайны по формуле <tex>d_i = \min\{d_i, n\}</tex> (в оптимальном расписании мы не выполняем работы позже времени <tex>t=n</tex>).
В результате выполнения данного алгоритма будет получено корректное расписание, в котором каждая работа встречается не более одного раза. Оптимальность полученного расписания доказывается аналогично [[1sumwu|<tex>1 \mid \mid \sum w_{i}U_{i}</tex>]].
