== Время работы ==
Время работы алгоритма зависит от того, насколько быстро мы будем добавлять и удалять работы из множества <tex> S </tex>, а также как быстро мы будем искать работу с минимальным весом. Если в качестве множества <tex> S </tex> использовать структуру данных, умеющую выполнять данные операции за <tex> O(\log n) </tex>, то время работы всего алгоритма будет составлять <tex> O(n\log n) </tex>. Например, такими структурами данных являются [[Двоичная куча | двоичная куча]] и [[Красно-черное дерево | красно-черное дерево]].
== Более простой случай ==
Задачу <tex> 1 \mid p_{i}=1 \mid \sum\nolimits U_i</tex> можно решить за <tex>O(n)</tex>. Рассмотрим следующий алгоритм. Работы, значение <tex>d</tex> у которых больше либо равно <tex>n</tex>, поместим в конец расписания. Для остальных работ заведём <tex>n-1</tex> множество <tex>S_{1}, S_{2} \dots S_{n-1}</tex>. В множестве <tex>S_{i}</tex> будем хранить номера работ, у которых <tex>d = i</tex>. Далее для каждого множества будем по очереди добавлять работы, которые успеваем сделать, в расписание (как в строчках 3-6 предыдущего алгоритма). Те работы, которые не успеваем сделать, добавим в конец расписания. Всего будет выполнено O(n) операций и время работы алгоритма, таким образом, составляет <tex>O(n)</tex>.
== Источники информации ==
