81
правка
Изменения
м
→Декомпозиция
'''<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>
'''int''' ans = f[l](e)
b.jobs.remove(l) '''Block[]''' g = blocks(<tex> b \setminus l </tex>.jobs.p, b.jobs.rm)
'''for''' i = 2 '''to''' g.size
schedule[g[i-1].end .. g[i].begin - 1] = l<font color = "darkgreen">// Вставляем работу в расписание между блоками</font> schedule[b.start .. g[1].start - 1] = l <font color = "darkgreen"> // Нужно учесть пропуски перед первым и </font> schedule[g[g.size].end .. b.end - 1] = l <font color = "darkgreen"> // после последнего блоков соответственно</font>
'''for''' b <tex>\in</tex> g
ans = max(ans, decompose(b, schedule).first)
