Объединение отрезков
Объединение отрезков
Решая задачу из контрольной по математике, Вася получил ответ в виде объединения n отрезков [li
, ri
] на числовой прямой. Однако, некоторые из этих отрезков могут пересекаться друг с другом, что не слишком нравится Васе.
Ваша задача - представить Васин ответ в виде объединения минимального количества отрезков.
Входные данные
В первой строке указано число n (1 ≤ n ≤ 50000). В следующих n строках перечислены пары целых чисел li
и ri
(|li
|, |ri
| ≤ 50000), каждая пара с новой строки, числа в парах отделены друг от друга одним или несколькими пробелами.
Выходные данные
В первой строке выведите число m - количество отрезков в искомом объединении. В следующих m строках выведите сами эти отрезки в том же формате, что и на входе. Список отрезков необходимо упорядочить по возрастанию левого конца.
4 0 2 4 5 1 3 5 6
2 0 3 4 6