Изменения
→Время работы
|statement= Задача <tex>Q | pmtn | Lmax</tex> может быть решена за <tex> O(n log(n) + mn) </tex> шагов.
|proof=
Решение <tex>Q | pmtn; ri | Cmax</tex> эквивалентно нахождению наименьшего <tex>T \ge 0</tex>, такого, что задача с "временными окнами" допустимым временным интервалом <tex>[r_i, T] (i = 1, . . . , n)</tex> имеет решение.
С другой стороны, решение <tex>Q | pmtn | Lmax</tex> эквивалентно нахождению такого наименьшего <tex>T \ge 0</tex>, такого, что задача с "временными окнами" временным интервалом <tex>[0, d_i + T]</tex> или с "временными окнами" <tex>[−T, d_i]</tex> имеет решение.
}}
Таким образом, задачи <tex>Q | pmtn; ri | Cmax</tex> и <tex>Q | pmtn | Lmax</tex> симметричны.
