Изменения
→Decompose
Decompose(B)
e = B.end <font color = "darkgreen"> //e — время завершения работ блока B.</font> 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)
start =
G = Blocks(<tex> B \setminus l </tex>)
'''for''' B[j] <tex>\in</tex> G
ans = max(ans, Decompose(B[j]))
Убедимся, что порядок выполнения работ, заданный графом зависимостей, не нарушается. Заметим, что в разбиении <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>, следует, что порядок выполнения будет правильным.
Также для корректности требуется, чтобы работы выполнялись не раньше, чем они появляются. Так как время выполнения работы определяется только в строке 4 строках 6-8 алгоритма, которая соответствует этому требованию, то условие выполняется.
Найдем теперь нижнюю оценку на <tex> f_{max} </tex>. Пусть <tex> f_{max}(J) </tex> — ответ для множества работ <tex> J </tex>.
