区间分组问题
1.将所有区间按照左端点从小到大排序
2.从前往后依次遍历每个区间:
判断能否将其放到某个现有的组中(当前区间左端点L[i] <= MAN_r)
2.1如果不存在这样的组,就开一个新的组,然后将其放入新组中
2.2如果存在这样的组,就将其放入组中,更新当前组的Max_r 为R[i]
#include<bits/stdc++.h>
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 main()
{
int n;
cin>>n;
for(int i = 0 ; i < n ; i ++)
{
int l,r;
scanf("%d%d",&l,&r);
range[i] = {l,r};
}
//1.按照左端点从小到大排序
sort(range,range+n);
//2.从前往后依次遍历每个区间
priority_queue<int,vector<int>,greater<int> >heap;
for(int i = 0; i < n ;i ++)
{
//如果不存在这样的组,就开一个新的组
if(heap.empty()||range[i].l <= heap.top())heap.push(range[i].r);
else//如果存在这样的组,就将其放入组中,并更新Max_r
{
heap.pop();
heap.push(range[i].r);
}
}
cout<<heap.size();
return 0;
}