AcWing 803. 区间合并
原题链接
简单
作者:
跟着灿哥学切菜
,
2021-01-13 19:58:03
,
所有人可见
,
阅读 208
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
vector<PII> segs;
void merge(vector<PII> &segs) {
vector<PII> res;
sort(segs.begin(), segs.end());
int st = -2e9, ed = -2e9;
//从前到后扫描线段
for (auto seg : segs) {
//此时ed表示正在维护的区间的右端点
if (ed < seg.first) {
//如果此时的区间不是初始区间, 则将这个区间加入到答案中
if (ed != -2e9) res.push_back({st, ed});
st = seg.first;
ed = seg.second;
} else {
//此时表示正在遍历的这个区间与维护的区间是有交集的
ed = max(ed, seg.second);
}
}
//如果最后的一个区间是单独存在, 此时需要将这个区间加入到最终的答案中
if (st != -2e9) res.push_back({st, ed});
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;
}