C++ 代码
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int,int> pii;
vector<pii> interval;
int main()
{
int n,l,r,res=0;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d%d",&l,&r);
interval.push_back({l,r});
}
sort(interval.begin(),interval.end());//左端点排序
/*每个区间的左端点与所有区间组中最小的右端点进行比较,如果大于则加入右端点最小的区间组并更新,
否则将作为一个新的组,左端点已经排过序,所以不用再考虑左端点的影响*/\
//用小根堆来存储每个组的右端点
priority_queue<int ,vector<int>,greater<int>>heap;//小根堆定义
for(auto i:interval)
{
if(heap.empty()||heap.top()>=i.first)//如果为堆空或者最小右端点大于等于当前区间左端点,则需新开一个区间组
{
heap.push(i.second);
res++;
}
else
{
heap.pop();//更新最小右端点并重新排序(排序在添加时自动进行)
heap.push(i.second);
}
}
printf("%d",res);
return 0;
}
//第二种做法
/*
大家可以把这个问题想象成活动安排问题有若干个活动,第i个活动开始时间和结束时间是[Si,Ei],同一个
教室安排的活动之间不能交叠,求要安排所有活动,少需要几个教室?同一个教室的活动视为同一组有时间
冲突的活动不能安排在同一间教室,与该问题的限制条件相同,即最小需要的教室个数即为该题答案。我们
可以把所有开始时间和结束时间排序,遇到开始时间就把需要的教室加1,遇到结束时间就把需要的教室减1,
在一系列需要的教室个数变化的过程中,峰值就是多同时进行的活动数,也是我们至少需要的教室数。
*/
// const int N=100010;
// int interval[2*N];
// int main()
// {
// int n,start,end,k=0,res=1,t=0;//res赋值为1,因为至少1组;t为需要的教室数
// scanf("%d",&n);
// for(int i=0;i<n;i++)
// {
// scanf("%d%d",&start,&end);
// interval[k++]=2*start;//开始时间存为偶数
// interval[k++]=2*end+1;//结束时间存为奇数,方便判断
// }
// sort(interval,interval+k);
// /*sort(first_pointer,first_pointer+n,cmp)
// 参数解释: 第一个参数是数组的首地址,一般写上数组名就可以,因为数组名是一个指针常量。
// 第二个参数相对较好理解,即首地址加上数组的长度n(代表尾地址的下一地址)。
// */
// for(int i=0;i<k;i++)
// {
// if(abs(interval[i]%2)==0)//遇到开始时间,有负数,所以不适合用1&
// {
// t++;
// res=max(res,t);
// }
// else//遇到结束时间
// {
// t--;
// }
// }
// printf("%d",res);
// return 0;
// }