3622
правки
Изменения
м
→Псевдокод
Алгоритм принимает на вход массив пар, где первый элемент является временем появления <tex>r_i</tex> работы, а второй её дедлайном <tex>d_i</tex>, и возвращает расписание, представленное массивом, где на позиции <tex>i</tex> стоит момент обработки работы <tex>i</tex>.
'''function''' scheduling(jobs: '''<int, int>[n]'''[n]) -> '''int[n]'''
sort(jobs) <font color=green>// сортируем работы в порядке неубывания времени появления</font>
'''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>.
