Union of Interval

题目描述

对于实数 $L$ 和 $R$，记 $[L,R)$ 为所有大于等于 $L$ 且小于 $R$ 的实数的集合。这样的集合称为右开左闭区间（half-open interval）。 给定 $N$ 个右开左闭区间 $[L_i,R_i)$。令 $S$ 为它们的并集。将 $S$ 表示为最少数量的右开左闭区间的并。

输入格式

输入按下列格式由标准输入给出： $N$ $L_1$ $R_1$ $\vdots$ $L_N$ $R_N$

输出格式

令 $k$ 为表示 $S$ 为若干右开左闭区间并所需的最小区间数。按 $X_i$ 的升序打印 $k$ 行，包含这样的 $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

3
10 40
30 60
20 50

10 60

提示

$1 \leq N \leq 2\times 10^5$ $1 \leq L_i \lt R_i \leq 2\times 10^5$ 输入中的所有值均为整数。三个右开左闭区间 $[10,20),[20,30),[40,50)$ 的并等于两个右开左闭区间 $[10,30),[40,50)$ 的并。
三个位于 $[10,40),[30,60),[20,50)$ 的并等于一个右开左闭区间 $[10,60)$ 的并。

标签: AtCoder|abc256D

来源

AtCoder|abc256D