4110: 区间的并集
内存限制：1024 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
# Union of Interval
## 题目描述
对于实数 $L$ 和 $R$，我们用 $[L,R)$ 表示大于等于 $L$ 且小于 $R$ 的实数集合。这样的集合被称为右半开区间。
给定 $N$ 个右半开区间 $[L_i,R_i)$。设 $S$ 为它们的并集。将 $S$ 表示为最少数量的右半开区间的并集。
输入
## 输入格式
输入从标准输入中给出，格式如下：
$N$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_N$ $R_N$
输出
## 输出格式
设 $k$ 为表示 $S$ 所需的最少右半开区间数。按 $X_i$ 升序输出这 $k$ 个右半开区间 $[X_i,Y_i)$，格式如下：
$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_k$ $Y_k$
样例输入 复制
3
10 20
20 30
40 50样例输出 复制
10 30
40 50提示
## 输入输出样例
### 输入样例1
```
3
10 20
20 30
40 50
```
### 输出样例1
```
10 30
40 50
```
### 输入样例2
```
3
10 40
30 60
20 50
```
### 输出样例2
```
10 60
```
## 数据范围与提示
【样例1说明】
三个右半开区间 $[10,20),[20,30),[40,50)$ 的并集等于两个右半开区间 $[10,30),[40,50)$ 的并集。
【样例2说明】
三个右半开区间 $[10,40),[30,60),[20,50)$ 的并集等于一个右半开区间 $[10,60)$ 的并集。
【数据范围】
- $1 \leq N \leq 2\times 10^5$
- $1 \leq L_i < R_i \leq 2\times 10^5$
- 输入中的所有值都是整数。
## 题目来源
ABC256D