1632
правки
Изменения
м
rollbackEdits.php mass rollback
<tex>d[k] = \min\{d[i] \mid i \in S\}</tex>
'''if''' <tex>d[k] \leqslant time</tex>
<font color=green>//расписание составить невозможно</font> '''return ''' ''false'''
'''else'''
<font color=green>//выполняем работу номер <tex>k</texfont>
<tex>S = 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>S = S \cup \{j\}</tex>
<tex>j = j + 1</tex>
<tex>d[k] = \min\{d[i]</tex> | <tex>i \in S\}</tex>
'''if''' <tex>d[k] \leqslant time</tex>
<font color=green>//расписание составить невозможно</font> '''return ''' ''false'''
'''else'''
<font color=green>//выполняем работу номер <tex>k</texfont>
<tex>S = 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>, например [[Двоичная_куча|двоичная куча]].
