AcWing 906. 区间分组
原题链接
简单
作者:
月亮_7
,
2024-04-07 21:28:23
,
所有人可见
,
阅读 1
//区间分组,组内两两没有交集
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
//1.所有区间按左端点从小到大排序
//2.从前往后处理每个区间
// 判断能否将其放到某个现有的组中,L[i]>Max_r
// 不存在这样的组,开一个新组,把区间放进去
// 存在这样的组,将其放进去,并更新当前组的Max_r
const int N=100010;
struct Range{
int l,r;
bool operator < (const Range &w)const
{
return l<w.l;
}
}range[N];
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
int l,r;
scanf("%d%d",&l,&r);
range[i]={l,r};
}
sort(range,range+n);
//定义一个小根堆,vector 作为底层容器
priority_queue<int,vector<int>,greater<int>> heap;
for(int i=0;i<n;i++)
{
auto R=range[i];
//如果一个区间的左端点比最小组的右端点要小,说明有交集
if(heap.empty()||heap.top()>=R.l) heap.push(R.r);
else {
//int t=heap.top();
heap.pop();
heap.push(R.r);
}
}
//区间当成一个人占用某物品的时间,谁先来(左端点小)谁先上,哪个物品先用完(右端点小)先腾出来哪个。
printf("%d\n",heap.size());
return 0;
}