OI题库

问题：

现给定n个闭区间[a_i, b_i]，1 £ i £ n。这些区间的并可以表示为一些不相交的闭区间的并。你的任务就是在这些表示方式中找出包含最少区间的方案。你的输出应该按照区间的升序排列。这里如果说两个区间[a, b]和[c, d]是按照升序排列的，那么我们有a £ b < c £ d。

任务：

请写一个程序：

l 在文本文件minprz.in中读入这些区间；

l 计算满足给定条件的不相交闭区间；

l 把这些区间按照升序输出到文件minprz.out中。

输入格式(minprz.in：

在文本文件PRZ.IN的第一行包含一个整数n，3 £ n £ 50000，为区间的数目。以下n行为对区间的描述，第i行为对第i个区间的描述，为两个整数1 £ a_i £ b_i £ 1000000，表示一个区间[a_i, b_i]。

输出格式：

你应该在文本文件PRZ.OUT中输出计算出来的不相交的区间。每一行都是对一个区间的描述，包括两个用空格分开的整数，为区间的上下界。你应该把区间按照升序排序。

样例：

输入（minprz.in）:

5

5 6

1 4

10 10

6 9

8 10

输出（minprz.out）：

1 4

5 10