=== Decompose ===
Идея следующая: допустимДопустим, у нас есть блок работ, который можно выполнить без прерываний. Найдем Общая идея алгоритма Decompose следующая: найдем работу <tex>i</tex>, которую выгодно выгоднее всего выполнить последней. Разобъем оставшееся множество работ на блоки, решим задачу для этих блоков рекурсивно и вставим <tex> i </tex> в промежутки между этими блокаминими, до них и после них, начиная с <tex> r_i </tex>.Псевдокод этого алгоритма представлен ниже. Decompose(B) 1 найти <tex> l: f_l(e) = \min \{f_j(e) \mid j \in B, \overline\exists\ k: jk \in E \} </tex> 2 ans <tex> \leftarrow f_l(e) </tex> 3 G <tex> \leftarrow </tex> Blocks(<tex> B \setminus l </tex>) 4 вставить l в промежутки между блоками G, начиная с <tex> r_l </tex> 5 '''for''' B_j <tex> \in G </tex>: 6 ans = max(ans, Decompose(B)) 7 return ans
=== Общий алгоритм ===
