Изменения

find <tex> l: f[l](e) = \min \{f[j](e) \mid j \in B, \overline\exists\ k: jk \in E \} </tex>

ans = f[l](e)

G = Blocks(<tex> B \setminus l </tex>)

'''for''' i = 2 '''to''' G.size

Убедимся, что порядок выполнения работ, заданный графом зависимостей, не нарушается. Заметим, что в разбиении <tex> B \setminus l </tex> на блоки существует не более одного блока <tex> B_0 </tex>, расположенного до момента времени <tex> r_l </tex> — иначе после вставки <tex> l </tex> в промежутки между блоками, <tex> B </tex> выполнялся бы с прерываниями. Далее, заметим, что все интервалы времени, на которые назначается работа из блока <tex> B_j </tex>, находятся внутри интервала <tex> [s_j; e_j] </tex>; это относится и к блоку <tex> B_0 </tex>. Из этих двух наблюдений, а также того, что все работы со временами появления меньше, чем <tex> r_l </tex>, будут помещены в блок <tex> B_0 </tex>, следует, что порядок выполнения будет правильным.

Найдем теперь нижнюю оценку на <tex> f_{max} </tex>. Пусть <tex> f_{max}(J) </tex> — ответ для множества работ <tex> J </tex>.