48
правок
Изменения
Нет описания правки
'''int''' j = 1 <font color=green>// последняя невыполненная работа</font>
'''int[n]''' ans <font color=green>// массив, куда будет записано расписание</font>
'''heapHeap<int>''' M <font color=green>// [[Двоичная куча|куча]], в которой будем хранить доступные на данный момент работы в порядке неубывания дедлайнов</font>
'''while''' j <= n
'''int''' time = jobs[j].first <font color=green>// время начала выполнения текущего блока работ</font>
'''int''' k = 0 <font color=green>// количество занятых станков в данный момент времени</font>
'''while''' M.notEmpty()
i = M.pop() <font color=green>// получаем доступную работу с наименьшим дедлайном </font>
ans[i] = t <font color=green>// назначаем работу i на время t</font>
[[Файл:Ppi1riintegerLmax bad.png|320px|thumb|right|Пример работы алгоритма при вещественных <tex>r_i</tex>]]
Внутренний цикл '''<tex>\mathrm{while''' }</tex> распределяет работы блоками, в которых они выполняются без простоя станков. После окончания такого блока, время начала выполнения следующего будет равно текущему значению <tex>r_j</tex>.
=== Асимптотика ===
Сначала мы сортируем работы, что занимает <tex> \mathcal{O}(n\log{n})</tex>. Далее идёт цикл, в котором мы <tex>n</tex> раз кладём элемент в кучу и <tex>n</tex> раз извлекаем, что также занимает <tex> \mathcal{O}(n\log{n})</tex> времени. В итоге всё вместе составляет асимптотику алгоритма <tex> \mathcal{O}(n\log{n})</tex>.
