AcWing 803. 区间合并
原题链接
简单
作者:
攒到100w就退休
,
2024-01-20 18:57:28
,
所有人可见
,
阅读 35
C++ 区间和并
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
/*
1.按区间左端点排序
2.当前区间 st ed
情况一 st ed 有交集
情况二 st ed 包含
情况三 st ed 无交集
*/
typedef pair<int, int> PII;
const int N = 100010;
vector<PII> segs;
int n;
void merge(vector<PII> &segs) {
vector<PII> ans;
int st = -2e9, ed = -2e9;
for(auto item : segs) {
if(ed < item.first) { // 如果当前维护的区间与下一个区间没有交集,则加入到答案中
if(ed != -2e9) // 并且此时的区间不是初始区间
ans.push_back({st, ed});
st = item.first;
ed = item.second;
} else { // 否则,当前区间和下一个区间有交集,就取ed较大的
ed = ed > item.second ? ed : item.second; // ed 取较大的那一个
}
}
if(ed != -2e9) { // 最后一个区间
ans.push_back({st, ed});
}
segs = ans;
}
int main() {
scanf("%d", &n);
for(int i = 0; i < n; i ++) {
int l, r;
scanf("%d %d", &l, &r);
segs.push_back({l, r}); // 接收区间
}
sort(segs.begin(), segs.end()); // pair 排序首先对第一个变量排序,然后第二个
merge(segs);
printf("%d", segs.size());
return 0;
}
小伙不错,继续加油