AcWing 803. 算法基础班--第一章--16.区间合并模板
原题链接
简单
作者:
初静
,
2021-01-24 22:11:42
,
所有人可见
,
阅读 300
算法基础班–第一章–16.区间合并模板
算法模板
void merge(vector<PII> &segs) {
vector<PII> res;
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});
st = seg.first, ed = seg.second;
}
else ed = max(ed, seg.second);
if (st != -2e9) res.push_back({st,ed});
segs = res;
}
两步:
- 将所有区间,按左端点从小到大排序
- 每次维护一个当前区间,从左到右遍历
两种情况:
- li <= R, R = max{R, ri}
- li > R, 则将[L, R] 存下来,放入数组,将[L, R] 更新为[li, ri],以此类推
本题完整代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII; // 所有区间存到pair<>类型的vector数组中
const int N = 100010;
int n;
vector<PII> segs;
void merge(vector<PII> &segs) { //用引用类型&segs
vector<PII> res; //结果也是vector<PII>类型
sort(segs.begin(), segs.end()); //将所有区间排序,sort()对pair<>排序是优先以左端点排序,再以右端点排
int st = -2e9, ed = -2e9; //设边界值 -∞,题目是10^9
for (auto seg : segs ) // 从前向后扫描分两种情况,if 和 else
if (ed < seg.first) { //1.当前区间右端点,严格小于枚举区间左端点
if (st != -2e9) res.push_back({st, ed}); //首先if判断掉初始区间,把当前维护区间加入到结果数组
st = seg.first, ed = seg.second; //更新维护的区间
}
else ed = max(ed, seg.second); //2.有交集,则求并集,右端点更新为维护的区间右端点和枚举区间右端点的最大值
if (st != -2e9) res.push_back({st,ed}); //把最后的区间假如答案中(指的是维护的区间)if()主要防止一开始输入为空区间
segs = res; //segs更新为res
}
int main() {
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;
}