264
правки
Изменения
→Решение
При этом, <tex>F_j(t) = \infty </tex> при <tex>t < 0, j = 0,\ldots, n </tex> и <tex>F_0(t) = 0 </tex> при <tex>t \geqslant 0 </tex>.
Ответом на задачу будет <tex>F_n(d_n)</tex>.
Приведенный ниже алгоритм вычисляет <tex>F_j(t)</tex> для <tex>j = 0,\ldots, n </tex> и <tex>t = 0,\ldots, d_j </tex>. За <tex>p_{max}</tex> обозначим самое большое из времен выполнения заданий.
отсортиртировать работы по неубыванию времен дедлайнов <tex>d_i</tex>
<tex> F_j(t) = F_{j}(d_j) </tex>
Время работы данного алгоритма {{---}} <tex>O(n \sum\limits_{i=1}^n p_i)</tex>.
t = d_n
