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