题目描述
実数 L,R に対して、L 以上 R 未満からなる実数の集合を [L,R) と表します。このような形で表される集合を右半開区間といいます。
N 個の右半開区間 [Li,Ri) が与えられます。これらの和集合を S とします。S を最小の個数の右半開区間の和集合として表してください。
输入格式
入力は以下の形式で標準入力から与えられる。
N L1 R1 ⋮ LN RN
输出格式
S が最小で k 個の右半開区間の和集合で表せるとする。そのような k 個の右半開区間 [Xi,Yi) を Xi の昇順で以下のように k 行出力せよ。
X1 Y1 ⋮ Xk Yk
题目大意
给出 n 个左闭右开区间。
求它们的并,用最少个左闭右开区间的并表示。
3
10 20
20 30
40 50
10 30
40 50
3
10 40
30 60
20 50
10 60
提示
制約
- 1 ≤ N ≤ 2× 105
- 1 ≤ Li < Ri ≤ 2× 105
- 入力に含まれる値は全て整数である
Sample Explanation 1
3 つの右半開区間 [10,20),[20,30),[40,50) の和集合は 2 つの右半開区間 [10,30),[40,50) の和集合と等しくなります。
Sample Explanation 2
3 つの右半開区間 [10,40),[30,60),[20,50) の和集合は 1 つの右半開区間 [10,60) と等しくなります。