atcoder#ABC256D. [ABC256D] Union of Interval

[ABC256D] Union of Interval

题目描述

実数 L,R L,R に対して、L L 以上 R R 未満からなる実数の集合を [L,R) [L,R) と表します。このような形で表される集合を右半開区間といいます。

N N 個の右半開区間 [Li,Ri) [L_i,R_i) が与えられます。これらの和集合を S S とします。S S を最小の個数の右半開区間の和集合として表してください。

输入格式

入力は以下の形式で標準入力から与えられる。

N N L1 L_1 R1 R_1 \vdots LN L_N RN R_N

输出格式

S S が最小で k k 個の右半開区間の和集合で表せるとする。そのような k k 個の右半開区間 [Xi,Yi) [X_i,Y_i) Xi X_i の昇順で以下のように k k 行出力せよ。

X1 X_1 Y1 Y_1 \vdots Xk X_k Yk Y_k

题目大意

给出 nn 个左闭右开区间。

求它们的并,用最少个左闭右开区间的并表示。

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\ \leq\ N\ \leq\ 2\times\ 10^5
  • 1  Li < Ri  2× 105 1\ \leq\ L_i\ \lt\ R_i\ \leq\ 2\times\ 10^5
  • 入力に含まれる値は全て整数である

Sample Explanation 1

3 3 つの右半開区間 [10,20),[20,30),[40,50) [10,20),[20,30),[40,50) の和集合は 2 2 つの右半開区間 [10,30),[40,50) [10,30),[40,50) の和集合と等しくなります。

Sample Explanation 2

3 3 つの右半開区間 [10,40),[30,60),[20,50) [10,40),[30,60),[20,50) の和集合は 1 1 つの右半開区間 [10,60) [10,60) と等しくなります。