贪心|A83500题解

题目分析
先看样例1：
输入为:
5 2 1 4 2 5
根据输入构图：

1---2---3---4---5
1---2-X-3---4
    2---3-X-4---5

由图可知：在请求1的右端点截断可以满足所有要求，输出1
再看样例2：
输入为：

9 5
1 8  2 7  3 5  4 6  7 9

根据输入构图：

1---2---3---4---5---6---7---8---9
1---------------------------8
    2-------------------7
        3-------5
            4-------6
                        7-------9

先将lastPlace设为请求1的最右节点，ans设为1
接着与下面的请求最左节点进行比较。
循环到最后一个请求时，发现lastPlace为7，与最左节点相同，
将ans增加1，输出结果为2

代码
代码分析在代码中已有注释

#include<bits/stdc++.h>
using namespace std;
struct Ques{ // 表示一个问题
    int l,r;
};
bool cmp(Ques x,Ques y){
    return x.r < y.r; // 以右节点
}
int main(){
    int n,m;
    cin>>n>>m;
    vector<Ques> a(m+1);
    for(auto i=1;i<=m;i++){
        cin>>a[i].l>>a[i].r;
        a[i].l = min(a[i].l,a[i].r);
        a[i].r = max(a[i].l,a[i].r)-1;
    }
    sort(a.begin()+1,a.begin()+1+m,cmp);
    int lastPlace=INT_MIN,ans=0;
    for(auto i=1;i<=m;i++){
        if(lastPlace < a[i].l){ans++;lastPlace = a[i].r;}
    }
    cout<<ans;
    return 0;
}

时间复杂度：$O(m)$
空间复杂度：$O(m)$