题目内容

给定一个二维整数数组 intervals，其中 intervals[i] = [start_i, end_i] 表示一个闭区间。

请将所有存在重叠部分的区间进行合并，返回合并后的区间集合。返回结果中的任意两个区间均不重叠，且所有区间的并集与原区间集合的并集相同。

约束条件

• 区间数量 $n$ 满足 $1 \leq n \leq 10^4$。
• 每个区间固定包含两个整数端点。
• 对任意区间 $[start_i, end_i]$，满足 $0 \leq start_i \leq end_i \leq 10^4$。

输入描述

第一行为一个整数 $n$ ，代表数组 $intervals$的长度。 接下来的$n$行，每行有两个整数$start_i, end_i$，代表第$i$个区间。

输出描述

每行输出一个区间，区间的数字以空格分隔。每个区间以$start_i$升序输出。

样例1

输入

5
1 4
2 3
5 8
7 9
10 12

输出

1 4
5 9
10 12

说明

输入共 5 个区间：$[1,4]$、$[2,3]$、$[5,8]$、$[7,9]$、$[10,12]$。

先看前两个区间，$[2,3]$ 完全落在 $[1,4]$ 内，所以合并后仍为 $[1,4]$。

接着 $[5,8]$ 与 $[7,9]$ 有重叠部分 $[7,8]$，合并为 $[5,9]$。

最后的 $[10,12]$ 与 $[5,9]$ 不重叠，单独保留。

合并结果按左端点升序为 $[1,4]$、$[5,9]$、$[10,12]$。

样例2

输入

4
1 3
3 5
5 6
8 10

输出

1 6
8 10

说明

输入区间为 $[1,3]$、$[3,5]$、$[5,6]$、$[8,10]$。

题目规定端点碰到一起也视为重叠，因此 $[1,3]$ 与 $[3,5]$ 会在端点 3 处重叠，继续与 $[5,6]$ 在端点 5 处重叠，三个区间合并为 $[1,6]$。

$[8,10]$ 与前一个区间的右端点 6 没有接触，单独保留。

所以结果为 $[1,6]$、$[8,10]$。

样例3

输入

1
0 10000

输出

0 10000

说明

只有一个区间 $[0,10000]$，它覆盖了本题端点允许的全部范围。

因为没有其他区间需要合并，所以结果就是 $[0,10000]$。

这也是对单区间边界情况的验证。