48
правок
Изменения
замечание
j++
[[Файл:Ppi1riintegerLmax bad.png|320px|thumb|right|Пример работы алгоритма при вещественных <tex>r_i</tex>]]
Внутренний цикл '''while''' распределяет работы блоками, в которых они выполняются без простоя станков. После окончания такого блока, время начала выполнения следующего будет равно текущему значению <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>.
=== Замечание ===
Стоит отметить тот факт, что если снять ограничение на целочисленность <tex>r_i</tex> и позволить им принимать вещественные значения, то представленный алгоритм перестанет строить оптимальное расписание, как видно из контрпримера.
== Доказательство корректности алгоритма ==
