Изменения

Отсортировать работы так===Описание алгоритма===Чтобы получить оптимальное расписание, чтобы будем строить максимальное множество <tex>d_1 \leqslant d_2 \leqslant \dots \leqslant d_nS</tex> тех работ, которые успеют выполниться. Само расписание тогда будет состоять из всех работ из <tex>S = \varnothing</tex> <tex>time = 0</tex> '''for''' i = 1 '''to''' n '''do''' '''if''' , упорядоченных по неубыванию дедлайнов. Во время сортировки стоит учитывать, что дедлайны могут значительно превосходить количество задач. В таком случае необходимо предварительно пересчитать дедлайны по формуле <tex>time < d_i</tex> <tex>S = S \cup min\{ i d_i, n\}</tex> (в оптимальном расписании мы выполняем все работы до времени <tex>time</tex> <code>+=</code> <tex>1</tex> Cортировку работ по неубыванию дедлайнов осуществляем с помощью сортировки подсчетом за <tex>O(n)</tex>, а значит и весь алгоритм будет работать за <tex>O(n)</tex>. Для упорядочивания дедлайнов будем использовать [[Карманная сортировка|карманную сортировку]].

В результате выполнения данного алгоритма будет получено корректное расписание, в котором каждая работа встречается не более одного раза. Оптимальность полученного расписания доказывается аналогично ===Псевдокод=== '''function''' schedule(d: '''int[[1sumwu|n]'''): '''list<int>''' '''list<int>''' S = <tex>\varnothing</tex> '''int''' time = 0 '''for''' i = 1 \mid \mid \sum w_{'''to''' n '''do''' d[i] = min(d[i], n) Сортиуем d '''for''' i}U_{= 1 '''to''' n '''do''' '''if''' time < d[i}] S = S <tex>\cup</tex>]].{i} time += 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>.  ===Корректность и оптимальность=Источники информации==* Peter BruckerВ результате выполнения данного алгоритма будет получено корректное расписание, в котором каждая работа встречается не более одного раза. «Scheduling Algorithms» {{---}} «Springer»Вначале расписания будут стоять все работы, 2006 гкоторые мы успеваем выполнить до дедлайна. Остальные работы дописываются в конец в произвольном порядке.  Оптимальность полученного расписания доказывается аналогично [[1sumwu|<tex>1 \mid \mid \sum w_{i}U_{---}i} 86 стр</tex>]]. {{---}} ISBN 978-3-540-69515-8

==Источники информации==* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 86 стр. {{---}} ISBN 978-3-540-69515-8 [[Категория: Дискретная математика Алгоритмы и алгоритмыструктуры данных]]