Изменения
→Описание решения
Этот алгоритм может быть реализованным с асимптотикой <tex>O(r \log r)</tex>.
Мы предполагаем, что <tex>d_i \ge geqslant 0</tex> для <tex>i = 1,\ldots,n</tex> и хотя бы для одной работы <tex>i</tex> <tex>d_i = 0</tex>. Иначе, вычтем из всех <tex>d_i</tex> минимальное значение по <tex>d_i</tex>.
Так как <tex>C_i \ge geqslant 1</tex> для всех <tex>i = 1,\ldots,n</tex> и <tex>d_i = 0</tex> справедливо <tex>L_i = C_i - d_i \ge geqslant 1</tex> как минимум для одной работы <tex>i</tex>. К тому же, можно предположить, что <tex>C_i \le leqslant r</tex>. Таким образом, работы с <tex>d_i > r - 1</tex>, то есть c <tex>L_i = C_i - d_i < 1</tex>, можно смело игнорировать. Они не влияют на значение улучшаемой функции <tex>\max(L_i)</tex>, так как для некого <tex>i</tex> <tex>L_i \ge geqslant 1</tex> можно выполнять эти работы в любом порядке после всех остальных. Для оставшихся операций <tex>O_{ij}</tex> мы имеем:
<tex>-r + 1 \le leqslant l(O_{ij}) = d_i - n_i + j \le leqslant r - 1</tex>
Каждую операцию мы кладём в соответствующий список (на самом деле это должен быть heap для хорошей асимптотики) <tex>L(k)</tex>, где <tex>k = l(O_{ij}) = d_i - n_i + j</tex> <tex>(-r + 1 \le k \le r - 1)</tex>. На втором шаге мы планируем операции соответственно возрастающему по номеру списка <tex>k</tex> порядку, где операции из одного списка могут выполнятся в произвольном порядке.
