Автор задачи: Даниил Орешников, разработчики: Даниил Орешников и Егор Юлин
Заметим следующий факт: если мы скажем, что отрезок $$$[a, b]$$$ «меньше» отрезка $$$[c, d]$$$ при $$$b < c$$$, то получится отношение частичного порядка, а ответом будет являться разбиение всех отрезков на минимальное количество возрастающих последовательностей. Это может быть подсказкой к решению: воспользуемся идеей из алгоритма поиска НВП за $$$\mathcal{O}(n \log n)$$$.
Но здесь, вместо поиска НВП, будем также обрабатывать отрезки по очереди слева направо, но поддерживать текущее «оптимальное» разбиение отрезков на группы. Под оптимальностью в данном случае будем понимать
Аккуратным рассмотрением двух вариантов разбиения на группы можно показать, что добавление нового отрезка в более «оптимальное» разбиение приводит к не менее оптимальному новому разбиению, значит поддержание такого разбиения приведет к ответу, соответствующему минимальному числу групп в разбиении.
Осталось только научиться поддерживать это оптимальное разбиение. Отсортируем все отрезки по их левой границе и будем поддерживать правые концы всех групп в дереве поиска. Тогда, чтобы добавить очередной отрезок $$$[l, r]$$$, достаточно
Действительно, добавление одного отрезка приводит к изменению правого конца ровно одной группы (либо к добавлению новой группы, если все $$$r_i \ge l$$$). Чтобы добиться лексикографически минимальной последовательности правых концов, следует заменить максимальный возможный $$$r_i$$$. Таким образом, все решение работает за $$$\mathcal{O}(n \log n)$$$.