/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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
出力
S が最小で k 個の右半開区間の和集合で表せるとする。そのような k 個の右半開区間 [X_i,Y_i) を X_i の昇順で以下のように k 行出力せよ。
X_1 Y_1 \vdots X_k Y_k
入力例 1
3 10 20 20 30 40 50
出力例 1
10 30 40 50
3 つの右半開区間 [10,20),[20,30),[40,50) の和集合は 2 つの右半開区間 [10,30),[40,50) の和集合と等しくなります。
入力例 2
3 10 40 30 60 20 50
出力例 2
10 60
3 つの右半開区間 [10,40),[30,60),[20,50) の和集合は 1 つの右半開区間 [10,60) と等しくなります。
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).