102563: [AtCoder]ABC256 D - Union of Interval
Description
Score : $400$ points
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)$.
Input
Output
得分：$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$行，表示这$k$个右半开区间$[X_i,Y_i)$，按$X_i$的升序排列：
$X_1$ $Y_1$ $\vdots$ $X_k$ $Y_k$
样例输入1
3 10 20 20 30 40 50
样例输出1
10 30 40 50
三个右半开区间$[10,20),[20,30),[40,50)$的并集等于两个右半开区间$[10,30),[40,50)$的并集。
样例输入2
3 10 40 30 60 20 50
样例输出2
10 60
三个右半开区间$[10,40),[30,60),[20,50)$的并集等于一个右半开区间$[10,60)$的并集。