Изменения

Алгоритм <tex>1 | r_{i}, d_{i}, p_{i}=1 | -</tex>: <tex>S:=\varnothing;</tex> <tex>j\leftarrow1= 1;</tex> <tex>time\leftarrow1= 1;</tex> <tex>FOR</tex> '''for''' <tex>i := 1</tex> <tex>TO</tex> '''to''' <tex>n</tex> <tex>DO</tex> <tex>BEGIN</tex>: <tex>IF</tex> '''if''' <tex>S==\varnothing</tex> <tex>THEN</tex>: <tex>BEGIN</tex> <tex>time:=r_{j}</tex> <tex>END</tex> <tex>WHILE</tex> '''while''' <tex>time==r_{j}</tex> <tex>DO</tex>: <tex>BEGIN</tex> Добавить <tex>S \leftarrow S \cup \{j</tex> в <tex>S\}</tex> <tex>j:=j+1;</tex> <tex>ENDd_{k} = min\{d_{i}</tex> Пусть | <tex>ki \in S</tex> и <tex>d_{k\}</tex> минимально <tex>IF</tex> '''if''' <tex>d_{k}\le time</tex> <tex>THEN</tex>: Расписание составить невозможно '''else''': <tex>ELSE</tex> <tex>BEGIN</tex> Удалить <tex>S \leftarrow S \setminus \{k</tex> из <tex>S\}</tex> <tex>time:=time+1;</tex> <tex>END</tex> <tex>END</tex>

Сложность алгоритма <tex>O(n\log n)</tex> если в качестве <tex>S</tex> использовать структуру, которая позволяет поиск элемента с минимальным <tex>d_{i}</tex> за <tex>O(\log n)</tex>.