81
правка
Изменения
→Декомпозиция
Допустим, у нас есть блок работ, который можно выполнить без прерываний. Общая идея алгоритма <tex>\mathrm{Decompose}</tex> следующая: найдем работу <tex> i </tex>, которую выгоднее всего выполнить последней. Разобъем оставшееся множество работ на блоки, решим задачу для этих блоков рекурсивно и вставим <tex> i </tex> в промежутки между ними, до них и после них, начиная с <tex> rm_i </tex>. Псевдокод этого алгоритма представлен ниже.
'''int''' e = b.end <font color = "darkgreen"> // e — время завершения работ блока B.</font>
find l: f[l](e) = <tex> \min \{f[j](e) \mid j \in B, \overline\exists\ k: jk \in E \} </tex>
'''int''' ans = f[l](e)
'''Block []''' g = blocks(<tex> b \setminus l </tex>)
'''for''' i = 2 '''to''' b.size
'''for''' j = g[i - 1].end '''to''' g[i].begin - 1
schedule[g[g.size].end to b.end - 1] = l
'''for''' b[j] <tex>\in</tex> g
ans = max(ans, decompose(b[j]).first) '''return''' <tex>\langle</tex>ans, schedule<tex>\rangle</tex>
{{Теорема
