Изменения

Заметим, что расписание состоит из непрерывных блоков, между которыми есть пропуски - — все поступившие работы выполнены, а новых работ ещё не появилось. Расписание может состоять из одного блока.

Рассмотрим первый блок, для которого не получилось составить расписание. Возьмем в нём первую работу, для которой не нашлось места. Пусть её индекс будет равен <tex>k</tex>. Попробуем вставить эту работу в расписание. До блока её вставить нельзя, так как <tex>r_{i}</tex> больше или равно времени начала блока. А в блоке нет пропусков, поэтому нужно поменять её с какой-то <tex>i</tex>-ойй, которая уже стоит в этом блоке расписания. У всех таких работ <tex>d_{i}</tex> меньше или равно <tex>\le d_{k}</tex>, так как в алгоритме мы каждый раз брали работу с минимальным <tex>d_{i}</tex>. Но <tex>i</tex>-ую ю работу нельзя выполнить после <tex>k</tex>-ойй. Значит <tex>k</tex>-ую ю работу выполнить нельзя.