Изменения

===Описание алгоритма===Чтобы получить оптимальное расписание, будем строить максимальное множество <tex>S</tex> тех работ, которые успеют выполниться. Само расписание тогда будет состоять из всех работ из <tex>S</tex>, упорядоченных по неубыванию дедлайнов. Во время сортировки стоит учитывать, что дедлайны могут значительно превосходить количество задач. В таком случае необходимо предварительно пересчитать дедлайны по формуле <tex>d_i = \min\{d_i, n\}</tex> (в оптимальном расписании мы выполняем все работы до времени <tex>time=n</tex>). Для упорядочивания дедлайнов будем использовать [[Карманная сортировка|карманную сортировку]]. ===Псевдокод=== '''function''' schedule(d: '''int[n]'''): '''list<int[]>''' '''list<int[]>''' S = []<tex>\varnothing</tex>

Сортиуем d подсчетом

time <code>+=</code> 1 '''return''' S Во избежание лишнего копирования массивов, мы можем делать проход по массиву блоков (bucket'ов) и для каждого блока проходить по спискам работ внутри него. Начальное значение <tex> time = 0</tex>. После рассмотрения очередной работы мы будем добавлять ее в расписание и увеличивать <tex> time</tex> на <tex>1</tex>. Тогда, если значение <tex> time</tex> становится равным номеру блока, то мы переходим к следующему блоку, а нерассмотренные задачи помечаем как просроченные и выполняем в конце. Работы с <tex>d_i = 0</tex> заранее отметим как просроченные. ===Время работы===Cортировку работ по неубыванию дедлайнов осуществляем с помощью карманной сортировки за <tex>O(n)</tex>, а значит и весь алгоритм будет работать за <tex>O(n)</tex>.

==Время работы=Корректность и оптимальность=== Cортировку работ по неубыванию дедлайнов осуществляем с помощью сортировки подсчетом за <tex>O(n)</tex>, а значит и весь алгоритм В результате выполнения данного алгоритма будет работать за <tex>O(n)</tex>. Во время сортировки стоит учитыватьполучено корректное расписание, что дедлайны могут значительно превосходить количество задачв котором каждая работа встречается не более одного раза. В таком случае необходимо предварительно пересчитать дедлайны по формуле <tex>d_i = \min\{d_iВначале расписания будут стоять все работы, n\}</tex> (в оптимальном расписании которые мы не выполняем успеваем выполнить до дедлайна. Остальные работы позже времени <tex>time=n</tex>)дописываются в конец в произвольном порядке.

==Корректность и оптимальность==В результате выполнения данного алгоритма будет получено корректное расписание, в котором каждая работа встречается не более одного раза. Оптимальность полученного расписания доказывается аналогично [[1sumwu|<tex>1 \mid \mid \sum w_{i}U_{i}</tex>]].