题目描述 Description
在一个数轴上有n条线段,现要选取其中k条线段使得这k条线段两两没有重合部分(端点可以重合),问最大的k为多少。
输入描述 Input Description
输入格式
输入文件的第1行为一个正整数n,下面n行每行2个数字ai,bi,描述每条线段。
数据范围及提示 Data Size & Hint
数据范围
对于20%的数据,n≤10;
对于50%的数据,n≤1000;
对于70%的数据,n≤100000;
对于100%的数据,n≤1000000,0≤ai<bi≤1000000。
分类标签 Tags 点此展开
题解:
贪心。按照右端点从小到大排序。第一条线段一定选。
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
#define N 1000100
struct node{
int l,r;
}a[N];
int n;
inline int cmp(const node &x,const node &y){
return x.r<y.r;
}
inline void read(int &x){//数据范围很大,为防止TLE,写的读入优化
register char ch=getchar();//ps:2s的视线,不写也可以AC
int f=1;x=0;
while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
}
int main(){
read(n);
for(int i=1;i<=n;i++){
read(a[i].l),read(a[i].r);
}
sort(a+1,a+n+1,cmp);
int k=1;node t=a[1];
for(int i=2;i<=n;i++){
if(a[i].l<t.r) continue;
else k++,t=a[i];
}
printf("%d
",k);
return 0;
}