D - 区间的并集

得分: $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$ 行，每行包含一个半开区间 $[X_i,Y_i)$，如下所示：

``` $X_1$ $Y_1$ $\vdots$ $X_k$ $Y_k$ ```

---

3
10 20
20 30
40 50

10 30
40 50

三个半开区间 $[10,20),[20,30),[40,50)$ 的并集等于两个半开区间 $[10,30),[40,50)$ 的并集。

---

3
10 40
30 60
20 50

10 60

三个半开区间 $[10,40),[30,60),[20,50)$ 的并集等于一个半开区间 $[10,60)$ 的并集。