贪心算法——区间选点

感觉和活动安排很类似。
算法思想：将区间按照右端点大小从小到大排列，用res记录取点数，遍历区间每次取区间的右端点如果和下个区间不相交，则res++。

//将每个区间按照右端点从小到大排序
//依次遍历每个区间选择右端点
#include<iostream>
#include<algorithm>
using namespace std;

const int N=100010;
struct Range{
    int l,r;
}range[N];

bool comp(Range w1,Range w2){
    return w1.r<w2.r;
}

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int l,r;
        cin>>l>>r;
        range[i]={l,r};
    }
    sort(range,range+n,comp);
    int res=0;int ed=-1e9;
    for(int i=0;i<n;i++){
        if(range[i].l>ed){//如果下个区间和当前区间不相交时
            res++;
            ed=range[i].r;
        }
    }
    cout<<res;
}