1226. 区间

时间限制 1000 ms   内存限制 128 MB

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

输入数据

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

输出数据

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

样例输入

复制
5 
5 6 
1 4
10 10
6 9
8 10
 \n
 · \n
 · \n
  ·  \n
 · \n
 ·  \n

样例输出

复制
1 4
5 10
 · \n
 ·  \n

提交

请先 登录

© 2024 FAQs Contact About