Изменения
Нет описания правки
<tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum f_i</tex>
<tex>f_{i}</tex> {{---}} монотонная функция времени окончания работы <tex>C_{i}</tex> для работ <tex>i = 1, 2, \dots ldots , n</tex>.
===Псевдокод===
<tex> S \leftarrow \{1 \dots ldots n\}</tex>
<tex> \mathtt{time} \leftarrow 0</tex>
<tex> \mathtt{answer} \leftarrow 0</tex>
'''while''' <tex> S \neq \varnothing </tex>
<tex> j \leftarrow null </tex>
'''if''' <tex> i \in S</tex> '''and''' <tex> r_{i} \leqslant \mathtt{time}</tex> '''and''' <tex>w_i \geqslant \max\limits_{j = 1 \dots ldots n} w_j</tex>
<tex> j \leftarrow i </tex>
'''if''' <tex>j \neq null </tex>
===Сложность алгоритма===
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max\limits_{i = 1 \dots ldots n} r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, [[:Категория:Приоритетные_очереди|очередь с приоритетами]]. Значит общее время работы алгоритма <tex>O((n + \max\limits_{i = 1 \dots ldots n} r_{i})\log n)</tex>
==См. также==
