洛谷P1803—凌乱的yyy / 线段覆盖【区间贪心】

洛谷P1803

输出：

输入：
3
0 2
2 4
1 3
输出：
2

思路：题意可以转化为找尽量多的不重复区间。
AC代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
struct Node
{int l,r;
}a[maxn];
bool cmp(const Node &a,const Node &b)
{if(a.r==b.r)//结束时间相同，按开始时间升序排序return a.l<b.l;return a.r<b.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 cnt=1;//第一场比赛最早结束，必选int now=1;//当前比赛为第一场比赛for(int i=2;i<=n;i++)if(a[i].l>=a[now].r)//某场比赛开始时间大于等于当前比赛结束时间{now=i;//更新cnt++;//又能多参加一场了}cout<<cnt<<endl;return 0;
}