分数: 400 点
问题陈述
对于实数 L 和 R,让我们表示为 [L,R) 大于或等于的实数集合 L 且小于 R。 这样的集合称为右半开区间。
你被给予 N 右半开区间 [L_i,R_i)。 让 S 成为他们的工会。 代表 S 作为右半开区间的最小数量的并集。
约束
- 1 \leq N \leq 2\times 10^5
- 1 \leq L_i \lt R_i \leq 2\times 10^5
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N L_1 R_1 \vdots L_N R_N
输出
让 k 是表示所需右半开区间的最小数量 S 作为他们的工会。 打印 k 行包含这样的 k 右半开区间 [X_i,Y_i) 按升序排列 X_i,如下:
X_1 Y_1 \vdots X_k Y_k
示例输入 1
3 10 20 20 30 40 50
示例输出 1
10 30 40 50
三个右半开区间的并集 [10,20),[20,30),[40,50) 等于两个右半开区间的并集 [10,30),[40,50).
示例输入 2
3 10 40 30 60 20 50
示例输出 2
10 60
三个右半开区间的并集 [10,40),[30,60),[20,50) 等于一个右半开区间的并集 [10,60).