Задача №113124. Объединение отрезков
Решая задачу из контрольной по математике, Вася получил ответ в виде объединения \(N\) отрезков \([L_i,R_i]\) на числовой прямой. Однако, некоторые из этих отрезков могут пересекаться друг с другом, что не слишком нравится Васе. От вас требуется представить Васин ответ в виде объединения минимального количества непересекающихся отрезков.
В первой строке входных данных дано число \(N\) (\(1\le N\le 30000\)). В следующих \(N\) строках перечислены пары целых чисел \(L_i\) и \(R_i\) (\(−50000\le L_i \le R_i \le 50000\)). Обратите внимание, что концы отрезков могут совпадать, в этом случае отрезок вырождается в точку.
В первой строке выведите число \(M\) — количество отрезков в искомом объединении. В следующих \(M\) строках выведите сами эти отрезки в том же формате, что и во входном файле. Список отрезков необходимо упорядочить по возрастанию левого конца.
4 0 2 4 5 1 3 5 6
2 0 3 4 6