AcWing 803. 区间合并
原题链接
简单
作者:
Asteroid.W
,
2021-08-26 14:50:13
,
所有人可见
,
阅读 206
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
void merge(vector<PII> &segs)
{
vector<PII> res; // 存储合并后的区间
sort(segs.begin(), segs.end()); // 所有区间按左端点排序
int st = -2e9, ed = -2e9; // 当前区间的左右端点,边界是1e9,大于边界就行了
for (auto seg : segs) // 从前往后扫描所有区间,分三种情况:完全覆盖,有交集,无交集。
if (ed < seg.first) // 当前区间与枚举的区间无交集,即找到了一个符合条件的区间
{
if (st != -2e9) res.push_back({st, ed}); // 如果不是初始的区间(初始时是负无穷到负无穷,也就是空),就添加到res里
st = seg.first, ed = seg.second; // 把这个枚举的区间更新成要维护的区间
}
else ed = max(ed, seg.second); // 否则,当前的区间和枚举的区间有交集,这个包含了两种情况:完全覆盖和有交集。然后取两个区间右端的最大值
if (st != -2e9) res.push_back({st, ed}); // 防止输入的数组里没有区间,防止是空的。把最后一个区间添加到res里
segs = res; // 把segs更新成res
}
int main()
{
int n;
scanf("%d", &n);
vector<PII> segs; // 存所有区间
for (int i = 0; i < n; i ++ )
{
int l, r;
scanf("%d%d", &l, &r);
segs.push_back({l, r}); // 把所有区间输入
}
merge(segs); // 调用区间合并的函数
cout << segs.size() << endl; // 返回区间个数
return 0;
}