577
правок
Изменения
→Псевдокод
Определим ''вектор частот'' <tex>h(t)</tex> {{---}} количество работ во временном интервале <tex>t</tex>. Работы отсортированы в порядке <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>.
'''function''' <tex>\mathrm{Scheduller}():</tex>
'''int''' <tex>h[]</tex>
'''vector<int>''' <tex>s[]</tex>
'''for''' <tex>t = 1</tex> '''to''' <tex>n</tex>
<tex>s[t] = \varnothing</tex>
'''for''' <tex>t = 1</tex> '''to''' <tex>m + n - 1</tex>
<tex>h([t) ] = 0</tex>
'''for''' <tex>i = 1</tex> '''to''' <tex>n</tex>
'''if''' <tex>d_i < m + i - 1</tex>
вычислим <tex>z</tex> {{---}} количество временных интервалов <tex>t = 1 \ldots d_i</tex>, таких, что <tex>h([t) ] < m</tex>
'''if''' <tex>z \geqslant m</tex>
<tex>T_i = d_i</tex>
вычислим <tex>m</tex> периодов <tex>1 \leqslant t_1 < t_2 < \ldots < t_m \leqslant T_i </tex> с минимальными значениями <tex>h(t_j)</tex>
'''for''' <tex>j = 1</tex> '''to''' <tex>m</tex>
<tex>s[i] = s[i] \cup \{t_j - 1\}</tex> <font color=green>// ставим работу <tex>i</tex> на время <tex>[t_j - 1, t_j]</tex></font> <tex>h([t_j) ] = h([t_j) ] + 1</tex>
=== Асимптотика ===
