Изменения
алгоритм
{{Задача
|definition=
Дано <tex>m</tex> однородных станков, работающих параллельно, и <tex>n</tex> работ с временем выполнения <tex>p_i = 1</tex> и , временем появления <tex>r_i</tex>, заданным целым числом, и момент времени <tex>d_i</tex>, к которому нужно выполнить работу. Необходимо построить такое расписание, чтобы значение максимального опоздания <tex>L_{max} = \max\limits_{i=1\ldots n} (C_i - d_i)</tex> было минимальным.
}}
== Описание алгоритма ==
=== Идея ===
Отсортируем все работы по времени появления в неубывающем порядке так, что <tex>r_1 \leqslant r_2 \leqslant \ldots \leqslant r_n</tex>. Теперь будем выполнять доступные на данный момент работы в порядке неубывания дедлайнов <tex>d_i</tex>. То есть, если в момент времени <tex>t</tex> есть свободные станки и есть невыполненные работы такие, что <tex>r_i \leqslant t</tex>, то назначаем работу с наименьшим дедлайном <tex>d_i</tex> на свободный станок.
=== Псевдокод ===
Алгоритм принимает на вход массив пар, где первый элемент является временем появления <tex>r_i</tex> работы, а второй её дедлайном <tex>d_i</tex>, и возвращает расписание, представленное массивом, где на позиции <tex>i</tex> стоит момент обработки работы <tex>i</tex>.
'''function''' scheduling(jobs: '''<int, int>'''[n]) -> '''int[n]'''
sort(jobs) <font color=green>// сортируем работы в порядке неубывания времени появления</font>
'''int''' j = 1 <font color=green>// последняя невыполненная работа</font>
'''int[n]''' ans <font color=green>// массив, куда будет записано расписание</font>
'''heap''' M <font color=green>// куча, в которой будем хранить доступные на данный момент работы в порядке неубывания дедлайнов</font>
'''while''' j <= n
'''int''' time = jobs[j].first
'''while''' jobs[j].first <= time <font color=green>// добавляем в кучу все невыполненные работы, доступные на данный момент</font>
M.push(j)
j++
'''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>
'''if''' k + 1 < m <font color=green>// если в момент t есть свободный станок, то назначаем работу i на него</font>
k++
'''else''' <font color=green>// иначе увеличиваем время и обновляем список доступных работ</font>
t++
k = 0
'''while''' jobs[j].first <= time
M.push(j)
j++
