37
правок
Изменения
Нет описания правки
'''Описание алгоритма'''
Нам нужно распределить <tex>n</tex> работ в разное время. Если мы назначим время <tex>t</tex> для работы <tex>i</tex> то цена будет <tex>f_i(t + 1)</tex>. Так как нужно рассмотреть заполнить <tex>n</tex> временных промежутков, задача может быть решена за <tex>O(n^3)</tex>. Функция <tex>f_i</tex> монотонно неубывающая, тогда работы в расписании надо располагать как можно раньше для получения верного решения. <tex>n</tex> временных интервалов <tex>t_i</tex> для <tex>n</tex> работ могут быть получены с помощью следующего алгоритма, где предполагается что работы нумеруются так:
<tex> r_1 \leqslant r_2 \leqslant \ldots \leqslant r_n</tex>
'''while''' <tex> S \neq \varnothing </tex>
<tex> j \leftarrow null </tex>
'''if''' <tex> i \in S</tex> '''and''' <tex> r_{i} \leqslant \mathtt{time}</tex> '''and''' <tex>w_i \max w_geqslant max_{ij = 1} ^n w_j</tex>
<tex> j \leftarrow i </tex>
'''if''' <tex>j \neq null </tex>
==Сложность алгоритма==
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max max_{i = 1}^n r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, [[Wikipedia:ru:Очередь с приоритетом (программирование)|очередь с приоритетами]]. Значит общее время работы алгоритма <tex>O((n + \max max_{i = 1}^n r_{i})\log n)</tex>
