3622
правки
Изменения
→Более простые варианты исходной задачи: выпилено неправильное решение
}}
==Простые Более простые варианты исходной задачи==
Перед решением основной задачи рассмотрим более простые.
===Задача Вариант 1===<tex dpi = "200"> 1 \mid p_i = 1\mid \sum C_i</tex>
Этот случай простейший. Ответом будет <tex>\sum_sum\limits_{k = 1}^n(k)</tex>, так как мы <tex>n</tex> раз сложим время окончания выполнения одной работы. В этом случае Воспользовавшись формулой суммы первых <tex>n</tex> членов арифметической прогрессии алгоритм <tex>S_n=\dfrac{a_1+a_n}2 \cdot n</tex> будет работает за <tex>O(1)</tex>, но если нужно вывести и само расписание, время работы будет <tex>O(n)</tex>.
===Задача Вариант 2===<tex dpi = "200"> 1 \mid p_i = 1\mid \sum w_i C_i</tex>
==Основная задача==
===Псевдокод===
====Реализация 1====
<tex> S \leftarrow \{1 \ldots n\}</tex>
<tex> \mathtt{time} \leftarrow 0</tex>
'''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 \in S, j = 1 \ldots n} w_j</tex>
<tex> j \leftarrow i </tex>
'''if''' <tex>j \neq null </tex>
<tex> \mathtt{time++}</tex>
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max\limits_{i = 1 \ldots n} r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, [[:Категория:Приоритетные_очереди|очередь с приоритетами]]. Значит общее время работы алгоритма <tex>O((n + \max\limits_{i = 1 \ldots n} r_{i})\log 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>r_i</tex>, из очереди <tex>\mathtt{Q}</tex> достаётся каждая работа, причём ровно один раз, аналогично для очереди <tex>\mathtt{P}</tex>, поэтому итоговая асимптотика времени работы алгоритма составляет <tex>O(n \log n)</tex>.
==См. также==
* [[Классификация задач]]
* [[1ridipi11outtreesumwc|<tex>1 \mid outtree \mid \sum w_i C_i</tex>]]
* [[1ridipi1|<tex>1 | r_{i}, d_{i}, p_{i}=1 | -</tex>]]
== Источники информации ==
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 19-20
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 38-39