区间合并
区间合并
用例演示
- 多个蓝色小区间可以合并为三个绿色区间
解题思路
- 情况1:无需改变当前区间
- 情况2:将当前区间的
end
向后延伸 - 情况3:当前区间的任务已经完成,可以将当前区间放入答案集中,并将原区间
start
和end
更新为粉色区间的start
和end
实现代码
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 100;
int n;
vector<PII> segs;
void merge(vector<PII> &segs){
vector<PII> res;
sort(segs.begin(), segs.end());
int start = -2e9, end = -2e9;
// 注意这里end也是-2e9,因为是从左边来的,不能是2e9,否则就比不了啦!
for(auto seg: segs){
if(end < seg.first){
if(start != -2e9){
res.push_back({start, end});
}
start = seg.first, end= seg.second;
}else{
end = max(end, seg.second);
}
}
// 将最后一段合并区间也放入答案中
if(start != -2e9)
res.push_back({start, end});
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;
}
Enjoy Reading This Article?
Here are some more articles you might like to read next: