Изменения

<tex>\max\{C_i - d_i \mid i = 1, \ldots, n\}</tex>

}}

Судя по условию, <tex>i</tex>-тая работа может характеризоваться двумя значениями: количество операций <tex>n_i</tex> и машиной, на которой была совершена первая операция. Пусть <tex>r = \overset{n}{\underset{i=1}{\sum}}N_i</tex> {{---}} общее количество операций.

<tex>\max\{C_i - d_i \mid i = 1, \ldots, n\}</tex>

* введём для каждой операции <tex>O_{ij}</tex> величину <tex>l(O_{ij}) = d_i - n_i + j</tex>,

Этот алгоритм может быть реализован с асимптотикой <tex>O(r \log r)</tex>.

Так как <tex>C_i \geqslant 1</tex> для всех <tex>i = 1,\ldots,n</tex> и <tex>d_i = 0</tex> справедливо <tex>L_i = C_i - d_i \geqslant 1</tex> как минимум для одной работы <tex>i</tex>. К тому же, можно предположить, что <tex>C_i \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 \geqslant 1</tex> можно выполнять эти работы в любом порядке после всех остальных. Для оставшихся операций <tex>O_{ij}</tex> мы имеем:

<tex>-r + 1 \leqslant l(O_{ij}) = d_i - n_i + j \leqslant r - 1</tex>

==Алгоритм==