AcWing 803. AC 803
原题链接
简单
作者:
七分糖
,
2019-11-24 20:43:13
,
所有人可见
,
阅读 1388
AC 803区间合并
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N = 100010;
struct node{
int start;
int end;
}a[N];
int n;
bool cmp(node c,node d){//结构体排序,保证左区间从小到大排序
return c.start < d.start;
}
int main(){
scanf("%d",&n);
for(int i = 0; i < n; i ++) scanf("%d%d",&a[i].start,&a[i].end);
sort(a,a+n,cmp);
//for(int i = 0; i < n; i ++) cout << a[i].start << ' ' << a[i].end << endl;
int s = a[0].start,e = a[0].end;
int ans = 1;//必定有一个区间
for(int i = 1; i < n; i++){
if(a[i].start <= e && a[i].end > e) e = a[i].end;//两种情况,有交集
else if(a[i].start > e) s = a[i].start,e = a[i].end, ans ++;//无交集
}
cout << ans << endl;
return 0;
}
码风舒服~
kk