148
правок
Изменения
→Псевдокод
==Псевдокод==
<tex> S \leftarrow \{1 \dots n\}</tex>
<tex> time \leftarrow 0</tex>
<tex> answer \leftarrow 0</tex>
while <tex> S \neq \varnothing </tex>
<tex> j \leftarrow i : (\max \limits_{i \in S, r_{i} \leq time} w_{i})</tex>
if <tex>j \neq null </tex>
<tex> S \leftarrow S \setminus j</tex>
<tex> Answer \leftarrow Answer + (time - r_{j})w_{j}</tex>
<tex> time++</tex>
==Сложность алгоритма==
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, очередь с приоритетами. Значит общее время работы алгоритма <tex>O((n + \max r_{i})\log n)</tex>
