Изменения

Перейти к: навигация, поиск

1sumu

71 байт убрано, 14:53, 29 мая 2016
Алгоритм
Будем добавлять в <tex>S</tex> работы в порядке неубывания значений <tex>d_j</tex>. Если вновь добавленная работа не успевает выполниться до дедлайна, то найдём и удалим из <tex>S</tex> работу с самым большим временем выполнения.
<span style="color:Green">// Отсортировать работы так, чтобы <tex>d_1 \leqslant d_2 \leqslant \dots \leqslant d_n</tex></span> <tex>S \leftarrow = \varnothing</tex>; <tex>time \leftarrow = 0</tex>; '''for''' i := 1 '''to''' n '''do''' <tex>S \leftarrow = S \cup \{ i \}</tex>; <tex>time</tex> <code>+=</code> <tex>p_i</tex>;
'''if''' <tex>t > d_i</tex>
находим в <tex>S</tex> работу <tex>j</tex> с наибольшим <tex>p_j</tex>; <tex>S = S \setminus\{j\}</tex>; <tex>time</tex> <code>-=</code> <tex>p_j</tex>;
Алгоритм будет работать за <tex>O(n \log n)</tex>.
Анонимный участник

Навигация