Обсуждение участницы:Анна

[math] O \mid p_{i,j} = 1, d_i \mid - [/math]

Задача:

Дано [math]m[/math] одинаковых станков, которые работают параллельно, и [math]n[/math] работ, которые необходимо выполнить в произвольном порядке на всех станках. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть время окончания [math]d_i[/math] — время, до которого она должна быть выполнена. Необходимо проверить, существует ли расписание, при котором все работы будут выполнены вовремя.

Описание алгоритма

Идея

Заметим, что если [math]d_i \lt m[/math], то очевидно, что [math]C_i \gt d_i[/math], следовательно, расписания не существует. Поэтому будем полагать, что [math]m \leqslant d_i[/math] для [math]i = 1 \ldots n[/math].