acwing906. 区间分组

分析

1. 将区间按l从小到大排序，根据range[i].l加入到不同的组中，以保证没有交集
2. 用小根堆存储区间的最右边的值，如果range[i].l比小根堆的值小，那么新建一个组，否则替换堆的r值。

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e5+10;

struct Range{
    int l,r;  
    bool operator<(const Range&w)const{
        return l<w.l;
    }
}range[N];
int n;
int main(){
    cin>>n;
    for(int i=0;i<n;i++)cin>>range[i].l>>range[i].r;
    sort(range,range+n);
    priority_queue<int,vector<int>,greater<int>>heap;//小根堆
    for(int i=0;i<n;i++){
        auto t=range[i];
        if(heap.empty()||heap.top()>=t.l)heap.push(t.r);//新建组
        else{
            heap.pop();
            heap.push(t.r);//替换堆的最大r值
        }
    }
    
    cout<<heap.size()<<endl;
    return 0;
}