区间分组

⬅ 返回

1、例题

2、分析

3、代码

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
const int MAX_INT = 0x3f3f3f3f;
typedef pair<int,int> PII;
const int N = 1e5+10;
struct Unit{
    int l,r;
};
Unit unit[N];
bool cmp(Unit u1,Unit u2)
{
    return u1.l<u2.l;
}
 
 
int main(){
    int n;
    cin>>n;
    int ans=1;
    for(int i=1;i<=n;i++)
    {
        cin>>unit[i].l>>unit[i].r;
    }
    //按左端点排序
    sort(unit+1,unit+1+n,cmp);
    //小根堆，保存所有集合的右端点，它的大小就是集合的个数
    priority_queue<int,vector<int>,greater<int>> pq;
    for(int i=1;i<=n;i++)
    {
	    // 当前区间不能放到现有集合中 即当前区间的左端点小于已有区间的右边界 即有重叠
        if(pq.size()==0 || unit[i].l<=pq.top()){
        // 新开一个集合，并将右端点放入
            pq.push(unit[i].r);
        }else{
        //更新放入集合的右端点
            pq.pop();
            pq.push(unit[i].r);
        }
    }
     //小根堆，保存所有集合的右端点，它的大小就是集合的个数
    cout<<pq.size()<<endl;
}