Изменения
Нет описания правки
'''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 n}^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 n}^n r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, [[:Категория:Приоритетные_очереди|очередь с приоритетами]]. Значит общее время работы алгоритма <tex>O((n + \max\limits_{i = 1\dots n}^n r_{i})\log n)</tex>
==См. также==
