81
правка
Изменения
→Декомпозиция
Допустим, у нас есть блок работ, который можно выполнить без прерываний. Общая идея алгоритма <tex>\mathrm{Decompose}</tex> следующая: найдем работу <tex> i </tex>, которую выгоднее всего выполнить последней. Разобъем оставшееся множество работ на блоки, решим задачу для этих блоков рекурсивно и вставим <tex> i </tex> в промежутки между ними, до них и после них, начиная с <tex> rm_i </tex>. Псевдокод этого алгоритма представлен ниже.
'''<tex>\langle</tex>int, int[]<tex>\rangle</tex>''' decompose('''Block''' b, '''int[]''' schedule):
'''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>
schedule[g[g.size].end to b.end - 1] = l
'''for''' b[j] <tex>\in</tex> g
ans = max(ans, decompose(b[j],schedule).first)
'''return''' <tex>\langle</tex>ans, schedule<tex>\rangle</tex>
