问题2458--合并区间

2458: 合并区间

时间限制: 2 Sec  内存限制: 256 MB
提交: 372  解决: 45
[提交] [状态] [讨论版] [命题人:]

题目描述

给定一组区间，合并所有重叠区间。
 
区间重叠定义为：一个区间与另一个区间交叉或一个区间完全包含另一个区间。

输入

第1行一个n，表示接下来有n个区间。
第2至n + 1行，每行两个数l 、r 用空格隔开，表示全闭区间的左右两端。 (1 ≤ n ≤ 10000, 0 ≤ l ≤ r ≤ 1000000)

输出

输出合并后的区间，每行两个用空格隔开的数字，表示区间的左右两端，你应该按左区间升序输出。

样例输入

4
1 3
2 6
8 10
15 18

样例输出

1 6
8 10
15 18

提示

 

来源/分类

 

[提交] [状态]