90
правок
Изменения
→Описание алгоритма
Будем также рассматривать тайм-слоты без номеров работ: в каждом тайм-слоте просто лежит сколько-то единиц работ. От этого итоговый фронт также не изменится. Заметим, что если нельзя составить корректную в плане наполненности конфигурацию тайм-слотов при данном ослаблении, то нельзя это сделать и в случае существования номера у каждой единицы работы. Будем рассматривать тайм-слоты по убыванию времени с <tex>d_1</tex> до <tex>0</tex>. В каждый момент времени будем хранить сколько работ ''необходимо'' перекинуть на более ранние тайм-слоты. Изначально это число равно нулю.
Рассмотрим очередной тайм-слот. Пусть в нем занято <tex>h</tex> ячеек из <tex>m</tex>, а также, есть еще <tex>a</tex> нераспределяемых позже единиц работы. Здесь возможны два случая:* <tex>h + a > m</tex>. В этом случае, так как более <tex>m</tex> единиц работы сейчас выполнить нельзя, а также, ничего нельзя назначить позже, то оказывается, что невыполняемых сейчас или позже работ стало <tex>h + a - m</tex>.
* Если <tex>h + a <= m</tex>. Здесь можно назначить все нераспределяемые позже работы на это время, и сбросить их счетчик.
