AcWing 803. 区间合并
原题链接
简单
作者:
现代修士o_O
,
2021-04-21 19:45:02
,
所有人可见
,
阅读 223
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int,int> PII;
vector<PII> segs;
void merge(vector<PII> &segs)
{
vector<PII> res;//中间数组,存储结果区间再赋值给segs,因为直接在segs上不好操作
sort(segs.begin(), segs.end());
int st = -2e9, ed = -2e9;//初始维护的区间,绝对与其他的区间没有交集
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 为空这种情况
segs = res; // 赋值回来
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i ++ )
{
int l, r;
cin >> l >> r;
segs.push_back({l, r});
}
merge(segs);
cout << segs.size() << endl;
return 0;
}