/ Vijos / 题库 /

区间

区间

背景

描述

给定n个闭区间 [ai,bi], i=1,2,...,n. 这些区间的和可以用两两不相交的闭区间的和来表示。你的任务是找到这样的区间数目最少的表示,且把它们按升序的方式写到输出文件中。当且仅当a <= b < c <= d时,区间[a; b] 、[c; d]才是升序
写一个程序完成以下任务:
读取区间
计算出满足上述条件的两两不相交的区间
把找到的区间按升序输出

格式

输入格式

第一行只有一个数n, 3 <= n <= 50000,代表区间数.第I+1行有两个数ai,bi,之间用一个空格隔开,分别表示区间[ai,bi]的起始和结束(1 <= i <= n),1 <= ai <= bi <= 1000000

输出格式

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

样例1

样例输入1

5 
5 6 
1 4
10 10
6 9
8 10

样例输出1

1 4
5 10

限制

各个测试点1s

提示

信息

ID
1439
难度
4
分类
其他 | 排序模拟 点击显示
标签
递交数
1406
已通过
559
通过率
40%
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

CSC WorkGroup 邀请赛II