Изменения

{| class="standard"! Очереди !! Пояснения !! |-|* <tex>\mathtt{Q}</tex>;{{---}} обычная [[Очередь | очередь]], в которой работы изначально располагаются в отсортированном по <tex>r_i</tex> порядке,* <tex>\mathtt{P}</tex>;{{---}} [[Приоритетные очереди |Очередь в которой будем хранить работыприоритетная очередь]] по максимуму.

Очередь с приоритетами для хранения веса работ подходящих по времени <tex> \mathtt{time} \leftarrow 1</tex> <tex> \mathtt{answer} \leftarrow 0</tex> '''while''' <tex>\mathtt{Q} \neq \varnothing </tex> '''and''' <tex>\mathtt{P} \neq \varnothing </tex> '''if''' <tex>\mathtt{Q} \neq \varnothing </tex> <tex> j \leftarrow \mathtt{Q.head()}</tex> '''if''' <tex>\mathtt{time} < r_j</tex> <tex>\mathtt{time} \leftarrow r_j</tex> '''while''' <tex> \mathtt{time} \geqslant r_j</tex> <tex>\mathtt{P.insert}(w_j)</tex> <tex>\mathtt{Q.pop()}</tex> '''if''' <tex>\mathtt{Q} = \varnothing </tex> '''break''' '''else''' <tex> j \leftarrow \mathtt{Q.head()}</tex>| <tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot \mathtt{P.extractMax()} </tex> <tex> \mathtt{time}\texttt{++}</tex>

Перед началом алгоритма [[Сортировка|отсортируем]] В начале работы сортируются по порядку неубывания времени появления и добавляем их в очередь <tex>\mathtt{Q}r_i</tex>. insert - функция добавления элемента в очередь с приоритетами <tex>\mathtt{P}</tex>. extractMax - функция извлекает максимальный вес , из очереди с приоритетами <tex>\mathtt{PQ}</tex>. pop - функция извлечения элемента из очереди <tex>Q</tex>. empty - функция проверяет есть ли в достаётся каждая работа, причём ровно один раз, аналогично для очереди элементы, если их нет то вернет '''true''' в ином случая '''false'''.  <tex> \mathtt{time} \leftarrow r_1</tex> <tex> \mathtt{answer} \leftarrow 0</tex> '''while''' Q.empty() <tex>=</tex> '''false or''' P.empty() <tex>=</tex> '''false''' '''if''' Q.head() <tex>\neq null</tex> '''and''' <tex>\mathtt{time} \leqslant </tex> Q.head() <tex>\mathtt{time} \leftarrow</tex> Q.head() <tex>i \leftarrow </tex> Q.head() '''while''' <tex> r_i \leqslant \mathtt{time}</tex> P.insert(<tex>w_i</tex>) Q.pop() <tex>i \leftarrow </tex> Q.head() <tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \ \cdot </tex> P.extractMax() <tex> \mathtt{time++}</tex> В начале алгоритма сортируем работы <tex>O(n \log n)</tex> , поэтому итоговая асимптотика времени. Затем мы тратим <tex>O(n \log n)</tex> на получение ответа. Тогда суммарное время работы алгоритма составит <tex>O(n \log n + n \log n )</tex> что есть составляет <tex>O(n \log n)</tex> времени.