Изменения

Покажем, что данный алгоритм может быть реализован за время <tex>O(nm)</tex>.<br>Для начала рассмотрим следующий вопрос: пусть <tex>U</tex> {{---}} множество работ, для которого существует расписание, в котором отсутствуют опаздывающие работы, пусть <tex>i</tex> {{---}} работа, не принадлежащая <tex>U</tex>, для которой выполняется неравенство <tex>d_i \leqslant d_j</tex>для любой <tex>j \in U</tex>. Можно ли построить расписание для множества <tex>V = U \cup \{i\}</tex>, в котором так же будут отсутствовать опаздывающие работы.<br>Введем несколько обозначений. Вектора <tex>h</tex>, соответствующие множествам <tex>U</tex> и <tex>V</tex> обозначим как <tex>h^U</tex> и <tex>h^V</tex> соответственно. <tex>x(d_i)</tex> {{---}} количество временных интервалов <tex>t</tex> со свойствами*<tex>d_i - m + 1 \leqslant d_i</tex>,*<tex>h^U < m</tex>.Будем говорить, что работы могут быть выполнены ''вовремя'', если для них существует расписание, в котором эти работы успевают выполниться без опозданий. {{Лемма|statement=Пусть даны работы <tex>1, 2 \ldots i</tex> с дедлайнами <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant i</tex>, <tex>U = \{1, 2, \ldots i - 1\}</tex> и <tex>V = U \cup \{i\}</tex>. Тогда для всех работ <tex>j = d_i - m + 1 \ldots d_i</tex>, для которых <tex>h^U(j) < m</tex> будет верно, что <tex>h^V(j) = h^U(j) + 1</tex>.|proof=.}}