问题 5469. -- 区间数-【2014暑期训练】T4Day1T1

5469: 区间数-【2014暑期训练】T4Day1T1

时间限制: 1 Sec  内存限制: 256 MB
献花: 20  解决: 9
[献花][花圈]

题目描述

区间

【问题描述】

给定n个闭区间[ai,bi]( i=1,2...,n)。当某些区间重合或者重叠时,我们可以将这些区间合并成一个新的区间,以此来减少区间的个数。你的任务是将这n个区间用最少的区间数目表示,且把这些区间按升序的顺序输出到输出文件中。

当且仅当a <= b < c <= d时,区间[a,b] 、[c, d]才是升序。

【文件输入】

输入文件prz.in。

第一行只有一个数n(3 <= n <= 50000),代表区间数。

接下来n行,每行行有两个用空格隔开的数ai,bi,分别表示区间[ai,bi]的起始和结束(1 <= i <= n),(1 <= ai <= bi <= 1000000)。

【文件输出】

输出文件prz.out。

输出包含计算出的所有区间,每行写一个区间,每行只有两个数,分别是区间起始和结束,之间用一个空格分开。记住必须是按升序输出。

【输入样例】

5

5 6

1 4

10 10

6 9

8 10

 

【输出样例】

1 4

5 10

输入

输出

提示

来源

[献花][花圈]