管理咨询有限公司网站按天扣费优化推广

给定 N 个闭区间 [ai,bi]，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。

输出可选取区间的最大数量。

输入格式

第一行包含整数 N，表示区间数。

接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。

输出格式

输出一个整数，表示可选取区间的最大数量。

数据范围

1≤N≤105,
−109≤ai≤bi≤109

输入样例：

3
-1 1
2 4
3 5

输出样例：

2

_____________________________________________________________________________

用R,L记录当前重叠线段的左右端点；

分析：排完序后面对后面的线段只有3种情况：

      ——————————

1.                             ——————有重叠

2.                                            ————需要增加一条线段更新R,L;

写作不易，点个赞呗!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
_____________________________________________________________________________

#include <bits/stdc++.h>
using namespace std;
struct node{int l,r;
}a[1000005];
bool cmp(node a,node b){return a.r<b.r;
}
int n,ans=1,m;
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i].l>>a[i].r;}sort(a+1,a+1+n,cmp);int L=a[1].l,R=a[1].r;for(int i=2;i<=n;i++){if(a[i].l>R){L=a[i].l;R=a[i].r;ans++;}}	cout<<ans;	
}