Изменения

в произвольном порядке на всех станках. Время выполнения каждой работы на любом станке одинаково и равно одному.

Для каждой работы известно время, до которого её необходимо выполнить. Необходимо успеть выполнить как можно больше работ. }}

Отсортируем работы в порядке невозрастания дедлайнов.

При помощи построения паросочетаний было построено расписание для тех <tex>k</tex> работ, которые можно успеть сделать. Так как остальные работы уже нельзя успеть, расписание для них можно составить произвольное. Например, выполнять их по очереди после выполнения первых <tex>k</tex> работ.

Рассмотрим добавление очередной работы в тайм-слоты. За <tex>O(t)</tex> найдём переполнившийся тайм-слот и за <tex>O(m)</tex> перекинем из него элемент. Так как <tex>t=O(nm)</tex>, итоговая сложность этой части {{---}} <tex>O(n^2m)</tex>.