1632
правки
Изменения
м
Алгоритм <tex>1 | r_i, d_i, p_i=1 | -</tex>: '''function''' solve(r: '''int'''[n], d: '''int'''[n]):'''boolean'''
rollbackEdits.php mass rollback
Для начала решим более простую версию исходной задачи, когда все <tex>r_i=1</tex>.
====Описание алгоритма====
Будем выполнять работы в порядке возрастания их дедлайна <tex>d_i</tex>. Утверждается, что это оптимальное расписание.
Приведем реализацию, на основе которой мы вскоре построим решение основной задачи:
====Псевдокод====
Пусть <tex>S</tex> — множество еще не включенных в расписание задач. Изначально в нем находятся все задачи.
'''function''' solve(d: '''int'''[n]):'''boolean'''
<tex>S = \{1, 2, \ldots, n\}</tex>
'''int '''<tex>time = 1</tex> '''for''' <tex> i = 1 </tex> '''to''' <tex> n </tex>: <tex>d_k d[k] = \min\{d_i d[i] \mid i \in S\}</tex> '''if''' <tex>d_k d[k] \leqslant time</tex> Расписание <font color=green>// расписание составить невозможно</font> '''return''' ''false''
'''else'''
<font color=green>//выполняем работу номер <tex>k</texfont> <tex>S \leftarrow = S \setminus \{k\}</tex>
<tex>time = time + 1</tex>
'''return''' ''true''
Сложность алгоритма <tex>\mathcal{O}(n\log n)</tex>, если в качестве <tex>S</tex> использовать структуру, которая позволяет поиск элемента с минимальным <tex>d_i</tex> и его удаление за <tex>\mathcal{O}(\log n)</tex>, например [[Двоичная_куча|двоичная куча]].
====Доказательство корректности и оптимальности====
{{Теорема
Теперь перейдем к решению основной задачи.
====Описание алгоритма====
Теперь не все задачи доступны изначально. Однако утверждается, что очередную задачу теперь достаточно выбирать с минимальным <tex>d_{i}</tex> из всех, которые уже доступны. Если эта работа уже просрочена, значит хорошее расписание построить нельзя.
====Псевдокод====
Пусть <tex>S</tex> — множество ещё не включенных в расписание работ, к выполнению которых уже можно приступить. Изначально <tex>S</tex> пустое.
Отсортируем работы по порядку их появления.
<tex>S = \varnothing</tex>
'''int '''<tex>j = 1</tex> '''int '''<tex>time = 1</tex> '''for''' <tex> i = 1 </tex> '''to''' <tex> n </tex>:
'''if''' <tex>S == \varnothing</tex>
<tex>time=r_jr[j]</tex> '''while''' <tex>time==r_jr[j]</tex>: <tex>S \leftarrow = S \cup \{j\}</tex>
<tex>j = j + 1</tex>
<tex>d_k d[k] = \min\{d_id[i]</tex> | <tex>i \in S\}</tex> '''if''' <tex>d_k d[k] \leqslant time</tex> Расписание <font color=green>// расписание составить невозможно</font> '''return''' ''false''
'''else'''
<font color=green>//выполняем работу номер <tex>k</texfont> <tex>S \leftarrow = S \setminus \{k\}</tex>
<tex>time = time + 1</tex>
'''return''' ''true''
Сложность алгоритма <tex>\mathcal{O}(n\log n)</tex>, если в качестве <tex>S</tex> использовать структуру, которая позволяет поиск элемента с минимальным <tex>d_i</tex> и его удаление за <tex>\mathcal{O}(\log n)</tex>, например [[Двоичная_куча|двоичная куча]].
====Доказательство корректности и оптимальности====
{{Теорема
