4010 - 彩带管理

题目描述

在一条无限长的数轴上分布着若干条彩色线段,每条线段用一对坐标表示其起点和终点(包含端点)。

现在需要将这些线段进行合并处理,将所有重叠或相邻的线段合并成更长的连续线段。如果两条彩带区间 [a_i, b_i][a_j, b_j] 满足 a_i \leq a_j \leq b_i,则它们应当被合并。

最终输出所有合并后的独立线段(按起点坐标升序排列)。

输入

第一行,读入单个整数 n,表示初始彩带的数量。

第二行到第 n+1 行:每行两个整数 a_ib_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
说明

样例 1 解释

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

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 3 枚
难度 入门


上一题 下一题