905. 区间选点

本题采用了贪心的做法，具体什么是贪心在这里不做具体解释
先说说菜鸡的思路，我认为该题就是求区间的交集个数，所以我分情况将第一个元素进行升序排序后依据如果两个区间有交集则t[i].first<=ed进行判断，这样会遗漏几种情况，所以找了很长时间的bug最终放弃了，真的太繁琐了而且情况那么多数据那么大怎么可能想周全
看了几位大佬的解析和y总的视频，原来他们的思路是区间选点，如果下一个区间内还包含这个点就直接跳过
这里有两种解法，分别是依据左端点排序和右端点排序：

左端点排序代码：

#include<iostream>
#include<algorithm>
using namespace std;
const int M=1e5+10;
pair <int,int>t[M];
int n;

int merge(){
    sort(t,t+n);//区间左排序
    int res=0;
    int st=-2e9;
    for(int i=0;i<n;i++){
        if(t[i].first>st)
        {
            res++;
            st=t[i].second;
        }
        else{
            st=min(st,t[i].second);
        }
    }
    return res;
}
int  main(){
cin>>n;
for(int i=0;i<n;i++){
    cin>>t[i].first>>t[i].second;
}
    int a=merge();
    cout<<a;
    return 0;
}

右端点排序代码：

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
struct W{
    int a,b;
    bool operator <(const W &w)const{//这里必须得加{}
    return b<w.b;
    }
}t[N];
int n;
int merge(){

    int res=0;
    sort(t,t+n);
    int ed=-2e9;
    for(int i=0;i<n;i++){
        if(t[i].a>ed){
            ed=t[i].b;
            res++;
        }
    }
    return res;
}
int main(){
    cin>>n;
    int a,b;
    for(int i=0;i<n;i++){
        cin>>a>>b;
        t[i]={a,b};
    }
    int res=merge();
    cout<<res;
    return 0;
}