题解 | 活动安排

#include <iostream>
#include <algorithm>

using namespace std;

const int N=2e5;

struct p
{
    int l,r;
    bool operator< (const p &W)const//重载，使sort能对结构体排序
    {
        return r < W.r;
    }
}arr[N];

int main()
{
    int T;
    cin>>T;
  //jingen
    for(int i=0;i<T;i++)
    {
        cin>>arr[i].l>>arr[i].r;
    }
    sort(arr,arr+T);
    int cnt=0,res=0;
    for(int i=0;i<T;i++)
    {
        if(arr[i].l>=res)
        {
            cnt++;
            res=arr[i].r;
        }
    }
    cout<<cnt;
}

贪心思想，即求最大不相交区间数目，将割断区间保存在结构体中，按照右端点排序，判断左端点是否重叠，若未重叠，则更新选中区间的右端点所在。参与链接