Задача на жадные алгоритмы

Задача. На окружности даны n дуг (отрезков), нужно выбрать максимальное по размеру подмножество не пересекающихся.

Решение задачи. Для начала скажем, как задаются дуги на окружности. Пусть окружность — зацикленный отрезок [0..M), а дуги (отрезки) окружности задаются парами L[i]..R[i]. Если R[i] < L[i], отрезок проходит через точку M.

Основная идея решения — найти точку, в которой можно разрезать окружность. Вернее так: выбрать отрезок i, который мы точно возьмём в ответ. Как только такой отрезок i зафиксирован, окружность можно разрезать, например в точке R[i].

Представляя все объекты на окружности, решать задачу не очень удобно. Поэтому, используя приём «удвоение окружности», перейдём на прямую.

Если у какого-то отрезка R[i] < L[i], то сделаем R[i] += M. 
Для любого отрезка L[i]..R[i] породим парный ему L[i]+M..R[i]+M

Теперь у нас есть 2n отрезков на прямой, а окружность с разрезом в точке x соответствует отрезок этой прямой [x..x+M), где 0 <= x < M.

Другой вариант решения за O(sort + nk), где k — размер множества-ответа на задачу. Оставим сортировку. А сразу после сортировки воспользуемся методом двух указателей и за O(n) для каждого отрезка i насчитаем следующий отрезок next[i], который мы бы взяли нашей жадностью (жадность: L[next[i]] > R[i], из таких next[i] = min).