Изменения
Нет описания правки
====Реализация 2====
Перед началом алгоритма [[Сортировка|отсортируем]] работы по порядку неубывания времени появленияи добавляем их в очередь <tex>Q</tex>.
insert - функция добавления элемента в очередь с приоритетами<tex>P</tex>. pop - функция извлечения элемента из очереди <tex>Q</tex>.
<tex> S \leftarrow \{1 \ldots n\}</tex>
<tex> j \leftarrow 1</tex>
'''while''' <tex> S \neq \varnothing </tex>
'''for''' <tex> i = j</tex> '''to''' <tex>n</tex> '''do''' '''ifwhile''' <tex>r_i \leqslant \mathtt{time}</tex> P.insert(<tex>w_i</tex>) '''else''' <tex>j = i</tex> '''break'''Q.pop() '''if''' <tex>k \in S</tex> '''and''' <tex>w_k \geqslant \max\limits_{h \in S, h = 1,\ldots,j} w_{h}</tex> <tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \ \cdot w_k</tex> <tex> S \leftarrow S \setminus k</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> времени.
