Score : $400$ points

问题描述

对于实数 $L$ 和 $R$，我们用 $[L,R)$ 表示所有大于等于 $L$ 且小于 $R$ 的实数集合。这样的集合被称为右半开区间。

现在给你 $N$ 个右半开区间 $[L_i,R_i)$。设它们的并集为 $S$。请将集合 $S$ 表示为尽可能少的右半开区间的并集。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

For real numbers $L$ and $R$, let us denote by $[L,R)$ the set of real numbers greater than or equal to $L$ and less than $R$. Such a set is called a right half-open interval.

You are given $N$ right half-open intervals $[L_i,R_i)$. Let $S$ be their union. Represent $S$ as a union of the minimum number of right half-open intervals.

Constraints

• $1 \leq N \leq 2\times 10^5$
• $1 \leq L_i \lt R_i \leq 2\times 10^5$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$

$L_1$ $R_1$

$\vdots$

$L_N$ $R_N$

Output

Let $k$ be the minimum number of right half-open intervals needed to represent $S$ as their union. Print $k$ lines containing such $k$ right half-open intervals $[X_i,Y_i)$ in ascending order of $X_i$, as follows:

$X_1$ $Y_1$

$\vdots$

$X_k$ $Y_k$

Sample Input 1

3
10 20
20 30
40 50

Sample Output 1

10 30
40 50

The union of the three right half-open intervals $[10,20),[20,30),[40,50)$ equals the union of two right half-open intervals $[10,30),[40,50)$.

Sample Input 2

3
10 40
30 60
20 50

Sample Output 2

10 60

The union of the three right half-open intervals $[10,40),[30,60),[20,50)$ equals the union of one right half-open interval $[10,60)$.

update @ 2024/3/10 10:53:39