Изменения

Для верного выполнения просто выставим работы по порядку невозрастания весов, тогда ответом будет <tex> \sum\limits_{i = 1}^n(w_i C_i)</tex>, так как мы <tex>n</tex> раз сложим время окончания выполнения одной работы (которое в нашем случае <tex>C_{i-1}+1</tex>) домноженное на вес этой работы. То есть решаем жадным алгоритмом:  Покажем что алгоритм [[Методы_решения_задач_теории_расписаний|жадного построения расписания]] корректен. <tex>w_i C_i \geqslant w_j C_j</tex>, где <tex>w_i C_i</tex> произведение на каждом текущем шаге получаем до сортировки, а <tex>w_j C_j</tex> после. Полученное произведение <tex>w_j C_j</tex> «более похоже» на оптимальное решение и в результате , чем произведение <tex>w_i C_i</tex>. Тогда применение жадного алгоритма дает верный ответ.  Вес работ [[Сортировка|отсортировали]] за <tex>O(n \log n)</tex>. Алгоритм работает за <tex>O(n + n \log n)</tex>

Перед началом алгоритма [[Сортировка|отсортируем]]работы по порядку неубывания веса.