14
правок
Изменения
Нет описания правки
==Алгоритм==
Чтобы получить оптимальное расписание, будем строить максимальное множество <tex>S</tex> тех работ, которые успеют выполниться. Само расписание тогда будет состоять из всех работ из <tex>S</tex>, упорядоченных по неубыванию дедлайнов.Будем добавлять в Во время сортировки стоит учитывать, что дедлайны могут значительно превосходить количество задач. В таком случае необходимо предварительно пересчитать дедлайны по формуле <tex>Sd_i = \min\{d_i, n\}</tex> (в оптимальном расписании мы не выполняем работы в порядке неубывания значений позже времени <tex>d_jtime=n</tex>, если успеваем их выполнить). Для упорядочивания дедлайнов будем использовать карманную сортировку(bucket sort).
===Псевдокод===
schedule(d: '''int[n]'''): '''int[]'''
'''int[]''' S = []
'''for''' i = 1 '''to''' n '''do'''
d[i] = min(d[i], n)
Сортиуем d подсчетом
'''for''' i = 1 '''to''' n '''do'''
'''if''' time < d[i]
time <code>+=</code> 1
'''return''' S
Во избежание лишнего копирования массивов, мы можем делать проход по массиву блоков(bucket'ов) и для каждого блока проходить по спискам работ внутри него. Начальное значение <tex> time = 0</tex>. После рассмотрения очередной работы мы будем добавлять ее в расписание и увеличивать <tex> time</tex> на 1. Тогда, если значение <tex> time</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>]].
== См. также ==
