选择不相交区间

题目描述

数轴上有\(n\)开区间\((a_i，b_i)\),请选择尽量多的区间，使其两两不相交。(开区间意味着，左右两个端点是不包含的）

输入格式

第一行\(n\)

之后\(n\)行，每行两个数分别为\(a_i，b_i\)

输出格式

最多能选择的区间个数

样例

样例输入1

3
1 3
2 4
3 5

样例输出1

2

数据范围

对于\(20\%\)的数据，\(n≤10\)；

对于\(50\%\)的数据，\(n≤1000\)；

对于\(70\%\)的数据，\(n≤100000\)；

对于\(100\%\)的数据，\(n≤1000000，0≤ai＜bi≤1000000\)。

代码

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