AcWing 908. 最大不相交区间数量
原题链接
简单
作者:
Yaseal
,
2023-07-16 14:50:10
,
所有人可见
,
阅读 75
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N 100010
typedef struct node{
int a,b;
}Node;
Node u[100010];
int cmp(const void *a,const void *b){
Node *n1=(Node *)a;
Node *n2=(Node *)b;
return n1->b-n2->b;
}
int main() {
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d%d",&u[i].a,&u[i].b);
}
qsort(u,n,sizeof(Node),cmp);
int ans=0;
int r=-0x7fffffff;//注意这里表示最小int,如果不够小会被有些数据点hack
for(int i=0;i<n;i++){
if(u[i].a>r){
r=u[i].b;
ans++;
}
}
printf("%d\n",ans);
return 0;
}
- 注意最小int的表示方式,可以是-0x7fffffff,有时候-0x3fffffff都不一定稳妥