Слияние временных окон

Средняя

Орбитальный комплекс ведёт мониторинг гравитационных аномалий. За время дежурства было зафиксировано $n$ интервалов активности. Каждый интервал задаётся парой чисел $[l_i, r_i]$ — моментом начала и окончания аномалии.

Если два или более интервала пересекаются или соприкасаются (т.е. $r_i \ge l_j$ при $l_i \le l_j$ ), они объединяются в единое непрерывное окно наблюдения.

Найдите минимальный набор непересекающихся интервалов, полностью покрывающих все зафиксированные аномалии.

Входные данные

В первой строке задано целое число

n

(

1 \le n \le 10^5

) — количество интервалов.

В следующих

n

строках заданы по два целых числа

l_i

r_i

(

0 \le l_i \le r_i \le 10^9

) — границы интервалов.

Выходные данные

Выведите итоговые объединенные интервалы по одному в строке, упорядоченные по возрастанию времени начала. В каждой строке выведите два числа — левую и правую границу через пробел.

Примеры

Пример 1

Входные данные:

text

Выходные данные:

text

1 6
8 10
15 18

Примечание: Интервалы

[1, 3]

[2, 6]

перекрываются и объединяются в

[1, 6]

Пример 2

Входные данные:

text

2
1 4
4 5

Выходные данные:

text

1 5

Слияние временных окон

Средняя

Входные данные

В первой строке задано целое число

n

(

1 \le n \le 10^5

) — количество интервалов.

В следующих

n

строках заданы по два целых числа

l_i

r_i

(

0 \le l_i \le r_i \le 10^9

) — границы интервалов.

Выходные данные

Примеры

Пример 1

Входные данные:

text

Выходные данные:

text

1 6
8 10
15 18

Примечание: Интервалы

[1, 3]

[2, 6]

перекрываются и объединяются в

[1, 6]

Пример 2

Входные данные:

text

2
1 4
4 5

Выходные данные:

text

1 5

Код

Загрузка редактора...