AcWing 803. 区间合并
标签：sort include class using max 合并 一个 back fir
#include
#include
#include
using namespace std;
typedef pairint, int> PII;
void merge(vector &segs) {
vector res;
sort(segs.begin(), segs.end());//pair排序会优先以左端点排序
int st = -2e9, ed = -2e9;
for (auto seg : segs)
if (ed //没遇任何交集 ，说明找到了一个新的区间
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;
}
int main() {
int n;
scanf("%d", &n);
vector segs;
for (int i = 0; i ) {
int l, r;
scanf("%d%d", &l, &r);
segs.push_back({l, r});
}
merge(segs);
cout endl;
return 0;
}
AcWing 803. 区间合并
标签：sort include class using max 合并 一个 back fir
原文地址：https://www.cnblogs.com/QingyuYYYYY/p/11785053.html
评论