264
правки
Изменения
Нет описания правки
А именно, покажем, что решение задачи состоит в сопоставлении <tex>n</tex> различным заданиям различных времен начала выполнения работы. Если сопоставляем работе <tex>i</tex> время <tex>t</tex>, то вклад в целевую функцию будет <tex> f_i(t + 1) </tex>.
Далее будет показано, что при построении оптимального расписания нам нужно будет рассмотреть всего <tex>n</tex> различных времен начала работ. Следовательно, подобная задача может быть решена за <tex>\mathcal{O}(n^3)</tex>.
Поскольку <tex>f_i</tex> {{---}} монотонно неубывающие функции, то это значит, что в оптимальном расписании работы должны начинать исполняться как можно раньше. Первые <tex>n</tex> самых ранних для начала исполнения времен <tex>t_i</tex> могут быть вычислены следующим алгоритмом :
}}
==Частный случай==
В случае, когда все времена появлений заданий различны, оптимальное решение может быть посчитано за <tex>\mathcal{O}(n\log n) </tex>.
Поскольку любое задание выполняется за единицу времени, а все функции <tex>f_i</tex> являются неубывающими, то будет достаточно отсортировать работы по возрастанию времен появления и выполнять каждую работу как только она появится. Поскольку все <tex>r_i</tex> различны, то промежутки выполнения работ не будут пересекаться {{---}} расписание будет корректным.
