一、题目来源
AcWing算法基础课-803.区间合并
二、题目描述
给定 (n) 个区间 ([l_i,r_i]),要求合并所有有交集的区间。
注意如果在端点处相交,也算有交集。
输出合并完成后的区间个数。
例如:([1,3]) 和 ([2,6]) 可以合并为一个区间 ([1,6])。
输入格式
第一行包含整数 (n)。
接下来 (n) 行,每行包含两个整数 (l) 和 (r)。
输出格式
共一行,包含一个整数,表示合并区间完成后的区间个数。
数据范围
(1≤n≤100000,)
(−10^9≤l_i≤r_i≤10^9)
输入样例:
5
1 2
2 4
5 6
7 8
7 9
输出样例:
3
三、算法思路
本题可以抽象为一类题型,区间合并。
思路如下:
-
将所有的区间按照左端点从小到大的顺序进行排序。
-
使用 (st) 和 (ed) 分别表示当前区间的左端点和右端点,下一个区间会有以下三种情况:
1)(ed 时,由于已经排序过了,所以不能再继续合并了,将当前区间放入答案数组,并更新当前区间的左右端点。
2)(ed = l) 时,可以合并,更新右端点。
3)(ed > l) 时,可以合并,更新右端点。 -
最后特判一下,防止数据为空区间。
- 显然上述2、3种情况可以合并在一起。
- (st) 和 (ed) 的初始值应该要比所给的数据范围还要小,不然无法更新。
四、源代码
#include
#include
#include
using namespace std;
typedef pair PII;
const int N = 100010;
int n;
vector segs;
void merge(vector &segs)
{
vector res;
sort(segs.begin(), segs.end());
int st = -2e9, ed = -2e9;
for (auto seg : segs)
if (ed > n;
for (int i = 0; i > l >> r;
segs.push_back({l, r});
}
merge(segs);
cout
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net