==Алгоритм==
Идея ===1 | d_i, p_i=1 | -=== Для начала решим задачу, если все <tex>r_{i}=1</tex>, то есть <tex>1 | d_{i}, p_{i}=1 | -</tex>. Будем выполнять работы в порядке возрастания их дедлайна <tex>d_{i}</tex>. Утверждается, что это оптимальное расписание.Приведем реализацию, на основе которой мы вскоре построим решение основной задачи: Пусть <tex>S</tex> — множество еще не включенных в расписание задач. Изначально в нем находятся все задачи. <tex>S = \{1, 2, \ldots, n\}</tex> <tex>time = 1;</tex> '''for''' <tex> i = 1 </tex> '''to''' <tex> n </tex>: <tex>d_{k} = min\{d_{i}</tex> | <tex>i \in S\}</tex> '''if''' <tex>d_{k} \le time</tex>: Расписание составить невозможно '''else''': //выполняем работу номер <tex>k</tex> <tex>S \leftarrow S \setminus \{k\}</tex> <tex>time = time + 1;</tex> Сложность алгоритма <tex>O(n\log n)</tex>, если в томкачестве <tex>S</tex> использовать структуру, чтобы из тех работкоторая позволяет поиск элемента с минимальным <tex>d_{i}</tex> за <tex>O(\log n)</tex>. '''Доказательство корректности алгоритма''' Докажем от противного. Пусть в оптимальном расписании, где все работы укладываются в дедлайны, сначала идет работа <tex>i</tex>, а потом <tex>j</tex>, причем <tex>d_{i} > d_{j}</tex>. Посмотрим, что произойдет, если в расписании поменять их местами. Так как они обе выполняются за единицу времени, для всех задач, кроме <tex>i</tex>-й и <tex>j</tex>-й время их завершения <tex>C_{i}</tex> не поменялось. Для <tex>j</tex>-й же работы <tex>C_{j}</tex> стало меньше, что только лучше. <tex>C_{i}</tex> увеличилось и стало равно старому <tex>C_{j}</tex> однако, раз <tex>j</tex>-я работа раньше укладывалась в дедлайн, которые уже можно выполнитьто <tex>C_{i} = C_{j}^{old} \le d_{j} < d_{i}</tex>, ставить а значит и <tex>i</tex>-я работа все еще укладывается в расписание тусвой дедлайн, и наша замена ничего не испортила. ===1 | r_i, d_i, p_i=1 | -=== Теперь перейдем к основной задаче — <tex>1 | r_{i}, d_{i}, p_{i}=1 | -</tex>.Теперь не все задачи доступны изначально. Однако утверждается, у которой наименьшее что очередную задачу теперь достаточно выбирать с минимальным <tex>d_{i}</tex>из всех, которые уже доступны. Если эта работа уже просрочена, значит хорошее расписание построить нельзя.
Пусть <tex>S</tex> — множество ещё не включенных в расписание работ, к выполнению которых уже можно приступить. Изначально <tex>S</tex> пустое.
Расписание составить невозможно
'''else''':
//выполняем работу номер <tex>k</tex>
<tex>S \leftarrow S \setminus \{k\}</tex>
<tex>time = time + 1;</tex>
