题目描述
数轴上有 n 条线段，选取其中 k 条线段使得这 k 条线段两两没有重合部分，问 k 最大为多少。
输入格式
第一行为一个正整数 n；
在接下来的 n 行中，每行有 2 个数 a_i，b_i描述每条线段。
输出格式
输出一个整数，为 k 的最大值。
样例
样例输入
3
0 2
2 4
1 3
样例输出
2
数据范围与提示
对于 100% 的数据n<=1e6，0<=a_i<b_i<=1e6 。
_________________
简单贪心
_________________
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=1e6+10; 4 struct node 5 { 6 int l,r; 7 }sz[maxn]; 8 int n,ans; 9 bool cmp(node x,node y) 10 { 11 return x.r<y.r; 12 } 13 int main() 14 { 15 scanf("%d",&n); 16 for(int i=1;i<=n;++i)scanf("%d%d",&sz[i].l,&sz[i].r); 17 sort(sz+1,sz+1+n,cmp); 18 int rr=-1; 19 for(int i=1;i<=n;++i) 20 { 21 if(sz[i].l>=rr) 22 { 23 ans++; 24 rr=sz[i].r; 25 } 26 } 27 cout<<ans; 28 return 0; 29 }