748
правок
Изменения
→Псевдокод
==Псевдокод==
Предполагаем, что перед началом выполнения алгоритма выполняется, что 1 \leqslant d_{1} \leqslant d_{2} \leqslant ... \leqslant d_{n}. Все работы, дедлайн которых равен 0, мы в любом случае выполнить без штрафа не успеем, поэтому их изначально можно отнести к просроченным.
S {{---}} множество непросроченных работ, Check {{---}} функция, решающая задачу [[Opij1di|<tex> O \mid p_{i,j} = 1, d_i \mid - </tex>]].
S = <tex>\varnothing</tex>;
'''for''' i = 1 to n
S = <tex> S \cup \{i\} </tex>;
'''if''' ''not'' check(s) :
найти такое <tex>k</tex>, что <tex>w_{k} = \min \{ w_{j} \mid j \in S\}</tex>;
S = <tex>S \setminus \{k\}</tex>;
==Доказательство корректности==
