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