← 返回题目列表

AtCoder · abc256_d

G. 区间并集

中文机器翻译题面 查看原题

分数: 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).