问题 4897 --2.计算区间

4897: 2.计算区间

题目描述

  给定 $n$ 个闭区间 $[a_i,b_i]$。这些区间的和可以用几个两两不相交的闭区间的和来表示。
你的任务是按升序输出这样的区间数目最少的表示。当且仅当 $a \leq  b \leq c \leq d$ 时,区间 $[a,b]$、$[c,d]$ 才是升序。

输入

第一行只有一个数 $n$,代表区间数。
第 $i+1$ 行有两个数 $a_i,b_i$, 之间用一个空格隔开,表示区间 $[a_i,b_i]$。

输出

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

样例输入输出

输入#1 复制
5 
5 6 
1 4
10 10
6 9
8 10
输出#1 复制
1 4
5 10

提示

对于 $100\%$ 数据,$3 \leq n \leq 50000$ , $1 \leq a_i \leq b_i  \leq 10^6$ 。

序号 标题 作者 发表时间 费用 订购数 操作