Задача <tex>Q \mid pmtn; r_i \mid C_{max}</tex> представляет собой частный случай <tex>Q \mid pmtn; r_i \mid L_{max}</tex>, и может быть решена более эффективно. Labetoulle, Lawler, Lenstra, и Rinnooy Kan разработали алгоритм работающий за <tex> O(n log(n) + mn) </tex> специально для этого случая.
{{Утверждение
|statement= Задача <tex>Q \mid pmtn \mid L_{max}</tex> может быть решена за <tex> O(n log(n) + mn) </tex> шагов.
|proof=
Решение <tex>Q \mid pmtn; r_i \mid C_{max}</tex> эквивалентно нахождению наименьшего <tex>T \ge 0</tex>, такого, что задача с допустимым временным интервалом <tex>[r_i, T] (i = 1, . . . , n)</tex> имеет решение.
С другой стороны, решение <tex>Q \mid pmtn \mid L_{max}</tex> эквивалентно нахождению такого наименьшего <tex>T \ge 0</tex>, такого, что задача с временным интервалом <tex>[0, d_i + T]</tex> или <tex>[−T, d_i]</tex> имеет решение.
}}
Таким образом, задачи <tex>Q \mid pmtn; r_i \mid Cmax</tex> и <tex>Q \mid pmtn \mid L_{max}</tex> симметричны.
==Источники==
