Так как [[Сортировка|сортировка]] весов занимает <tex>O(n \log n)</tex> время, то асимптотика времени работы алгорита равна <tex>O(n + n \log n)</tex>.
===Вариант 3===
<tex> 1 \mid r_i,p_i = 1 \mid \sum f_i</tex>
<tex>f_{i}</tex> {{---}} монотонная функция времени окончания работы <tex>C_{i}</tex> для работ <tex>i = 1, 2, \ldots , n</tex>.
Нам нужно распределить <tex>n</tex> работ в разное время. Если мы назначим время <tex>t</tex> для работы <tex>i</tex> то цена будет <tex>f_i(t + 1)</tex>. Функция <tex>f_i</tex> монотонно неубывающая, тогда работы в расписании надо располагать как можно раньше для получения верного решения. <tex>n</tex> временных интервалов <tex>t_i</tex> для <tex>n</tex> работ могут быть получены с помощью следующего алгоритма, где предполагается что работы отсортированы так:
<tex> r_1 \leqslant r_2 \leqslant \ldots \leqslant r_n</tex>
'''Псевдокод'''
<tex>t_1 \leftarrow r_1 </tex>
'''for''' <tex> i \leftarrow 2</tex> '''to''' <tex>n</tex> '''do'''
<tex> t_i \leftarrow </tex> max<tex>(r_i, \ t_{i-1} - 1)</tex>
Этот алгоритм работает за <tex>O(n \log n +n)</tex>
==Основная задача==
===Описание алгоритма===
====Реализация 2====
Перед началом алгоритма * <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> S \leftarrow \{1 \ldots n\}</tex>Данная реализация имеет идею, аналогичную предыдущей: сначала обрабатывать работу с максимальным весом среди всех доступных. В начале работы сортируются по <tex> \mathtt{time} \leftarrow r_i</tex> , из очереди <tex> \mathtt{answerQ} \leftarrow 0</tex> <tex> j \leftarrow 1</tex> '''while''' <tex> S \neq \varnothing </tex> '''for''' <tex> i = j</tex> '''to''' <tex>n</tex> '''do''' '''if''' <tex>r_i \leqslant \mathtt{time}</tex> insert(<tex>w_i</tex>) '''else''' <tex>j = i</tex> '''break''' '''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{AnswerP} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot w_k</tex> <tex> S \leftarrow S \setminus k</tex> <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> времени.
==См. также==
