AcWing 没有用vector,自己想了个. 区间合并
原题链接
简单
作者:
未名湖畔的梦
,
2021-04-20 17:05:14
,
所有人可见
,
阅读 259
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 9;
struct OI{
int l, r;
}num[N];
int res, n;
inline int max(int &a, int & b){
return a < b ? b : a;
}
inline int cmp(OI a, OI b){
return a.l < b.l;
}
void combine(){
int st = num[1].l, ed = num[1].r;//维护两个指针
res++; //起始作为一个区间, 所以res起始为 1 个区间
for(int i = 2; i <= n; i++){
if(num[i].l <= ed){ // 可以合并成一个区间
ed = max(ed,num[i].r); // 这里区间是按左端点排序右端点不一定是排好序的
}
else{ // 不能合并成一个区间,res++ ,更新端点
st = num[i].l;
ed = num[i].r;
res++;
}
}
}
int main(){
scanf("%d",&n);
for(int i = 1, l, r; i <= n; i++){
scanf("%d%d",&l,&r);
num[i] = {l,r};
}
sort(num+1, num+1+n,cmp);
// for(int i = 1; i <= n; i++) printf("%d %d \n", num[i].l, num[i].r);
combine();
cout<<res<<endl;
return 0;
}