在一条无限长的数轴上分布着若干条彩色线段,每条线段用一对坐标表示其起点和终点(包含端点)。
现在需要将这些线段进行合并处理,将所有重叠或相邻的线段合并成更长的连续线段。如果两条彩带区间 [a_i, b_i] 与 [a_j, b_j] 满足 a_i \leq a_j \leq b_i,则它们应当被合并。
最终输出所有合并后的独立线段(按起点坐标升序排列)。
第一行,读入单个整数 n,表示初始彩带的数量。
第二行到第 n+1 行:每行两个整数 a_i 与 b_i 表示第 i 个彩带的起点和终点。
若干行,每行两个整数,表示合并后的彩带,这些彩带应该按照起点从小到大排序。
3 10 12 1 3 2 5
1 5 10 12
3 1 2 2 3 3 4
1 4
10 1 3 6 8 13 20 4 7 3 5 25 50 30 33 38 51 15 20 11 16
1 8 11 20 25 51
第 2 和 第 3 条彩带可以合并为一条 [1,5]。
最终还剩两条彩带,分别是 [1,5] 和 [10,12]。
对于 50 \% 的数据,满足 1 \leq n \leq 10^4, 0 \leq a_i \leq b_i \leq 10^4 。
对于 100 \% 的数据,1 \leq n \leq 10^5, 0 \leq a_i \leq b_i \leq 10^9 。