317
правок
Изменения
→Идея
Все работы хранятся в качестве вершин [[Классификация задач#Характеристики работ|intree-дерева]], состоящем из <tex>n</tex> вершин, нескольких корней и одного листа. В intree-дереве у одной вершины может быть два и более родителей.
Решение задачи состоит из двух шагов: на первом шаге мы меняем сроки выполнения работ в соответствии с их очередностью.
# Для Меняем делайны работ в соответствии с их очередностью: для всех <tex>i, j</tex> таких, что существует ребро из <tex>i</tex> в <tex>j</tex> будем менять <tex>{d_i}</tex> на <tex>\min ({d_i}, {d_j} - 1) </tex>.
# Работы расставляются в неубывающем порядке их дедлайнов.
