AT_abc256_d [ABC256D] Union of Interval

题目描述

对于实数 $L,R$，由所有满足 $L \leq x < R$ 的实数组成的集合记作 $[L,R)$。这种形式表示的集合称为右半开区间。

给定 $N$ 个右半开区间 $[L_i, R_i)$。它们的并集记作 $S$。请用最少数量的右半开区间的并集来表示 $S$。

输入格式

输入通过标准输入给出，格式如下：

$N$
$L_1$ $R_1$
$\vdots$
$L_N$ $R_N$

输出格式

假设 $S$ 可以用最少 $k$ 个右半开区间的并集表示。请按 $X_i$ 升序输出这 $k$ 个右半开区间 $[X_i, Y_i)$，每行一个区间：

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

输入输出样例 #1

输入 #1

3
10 20
20 30
40 50

输出 #1

10 30
40 50

输入输出样例 #2

输入 #2

3
10 40
30 60
20 50

输出 #2

10 60

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq L_i < R_i \leq 2 \times 10^5$
• 输入中的所有数值均为整数。

样例解释 1

$3$ 个右半开区间 $[10,20),[20,30),[40,50)$ 的并集等价于 $2$ 个右半开区间 $[10,30),[40,50)$ 的并集。

样例解释 2

$3$ 个右半开区间 $[10,40),[30,60),[20,50)$ 的并集等价于 $1$ 个右半开区间 $[10,60)$。

由 ChatGPT 4.1 翻译