AcWing 803. 区间合并
原题链接
简单
作者:
Koma
,
2022-02-21 17:48:58
,
所有人可见
,
阅读 154
思路
- pair存储题目给定区间
- merge里新建st,ed来表示当前维护区间
- 遍历所有区间,如果ed < 当前区间的左端点,则记录维护区间结果,更新维护区间为当前区间的上下限
- 否则更新ed看是否有更大的右端点
- 最后res的大小即为结果
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
typedef pair<int , int > PII;
vector<PII> segs;
void merge(vector<PII> &segs){
vector<PII> res;
int ed = -2e9, st = -2e9;//作为我们要维护的区间
sort(segs.begin(), segs.end());//默认按照左端点开始排序
for(auto seg : segs){
if(ed < seg.first){
res.push_back({st, ed});
st = seg.first;//更新维护区间的上下限
ed = seg.second;
}else ed = max(ed, seg.second);
}
segs = res;
}
int main(){
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++){
int l, r;
scanf("%d %d", &l, &r);
segs.push_back({l, r});
}
merge(segs);
cout<<segs.size();
}