洛谷P1803 凌乱的yyy / 线段覆盖

Question

---

分析：经典贪心应用之选择更多的区间，乱乱的区间肯定不利于我们思考，我们先将区间按右端点排个序，

这样右端点小的肯定是结束更早的，所以我们就一件一件事情选择，每次选择符合条件的右端点最小的即可

贪心策略：选择结束更早的

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

struct node
{
    int st,ed;
};
node a[1000005];
int n;

inline bool cmp(node x,node y)
{
    return x.ed<y.ed;
}

int main()   
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&a[i].st,&a[i].ed);
    sort(a+1,a+n+1,cmp);
    int ans=1,e=a[1].ed;
    for(int i=2;i<=n;i++)
    {
        if(a[i].st>=e)
        {
            ans++;
            e=a[i].ed;
        }
    }
    printf("%d",ans);
    return 0;
 }