恩施土家族苗族自治州网站建设_网站建设公司_jQuery_seo优化

题目链接：2402. 会议室 III（困难）

算法原理：

解法：堆+队列

69ms击败84.18%

时间复杂度O(Nlogn)

①会议排序：将所有会议按开始时间升序排列，保证按时间顺序处理每一场会议
②双优先队列初始化：
空闲队列：小顶堆（按会议室编号排序），优先分配编号小的空闲会议室；
使用队列：小顶堆（先按会议结束时间升序，结束时间相同时按会议室编号升序），优先获取最早结束 / 编号最小的可用会议室
③逐场处理会议：
释放：将当前会议开始前已结束的会议室从 “使用队列” 移回 “空闲队列”；
分配：有空闲会议室则直接分配，无空闲则等待 “使用队列” 中最早结束的会议室，同步延后当前会议的结束时间；
④记录：更新该会议室的使用次数，并将当前会议的结束时间 + 会议室编号加入 “使用队列”
结果统计：遍历统计数组，找到使用次数最多的会议室（次数相同选编号最小的）

答疑

Q1：为什么using队列的类型要用long[]型而不是int[]型呢？

因为处理过程中产生的延迟结束时间必须用long来存储，否则延后的太多int可能会溢出

Q2：为什么比较的是long但compare的返回值不能是long?

因为重写compare方法时，返回值必须是int，咱可以直接用Long.comapre()，因为它已经帮咱处理完long的类型且返回值也是int，也可以相减后强转成int，但不建议

Q3：为什么m是int[][]型的，比较器传的时候却是int[]型呢？为什么using队列是long[]型，比较器传的就是long[]型呢？为什么不是long呢？

就看你是根据什么比较的！

int[][] m的元素是int[]→比较器是Comparator<int[]>，比较两个int[]元素

PriorityQueue<long[]> using的元素是long[]→比较器是Comparator<long[]>，比较两个long[]元素

Java代码：

class Solution { public int mostBooked(int n, int[][] m) { //将所有会议按时间升序排序 // Arrays.sort(m,(a,b)->a[0]-b[0]); Arrays.sort(m,new Comparator<int[]>(){ @Override public int compare(int[] a,int[] b){ return a[0]-b[0]; } }); //建小根堆，优先分配编号小的空闲会议室 PriorityQueue<Integer> id=new PriorityQueue<>(); //初始化 for(int i=0;i<n;i++) id.offer(i); //正在使用的会议室 //格式[结束时间，会议室编号]先按结束时间排序，再把会议室编号小的放前面 //写法一 // PriorityQueue<long[]> using=new PriorityQueue<>( // (a,b)->a[0]!=b[0]?Long.compare(a[0],b[0]):Long.compare(a[1],b[1]) // ); //写法二： // PriorityQueue<long[]> using=new PriorityQueue<>( // (a,b)->a[0]!=b[0]?(int)(a[0]-b[0]):(int)(a[1]-b[1]) // ); //写法三： PriorityQueue<long[]> using=new PriorityQueue<>( new Comparator<long[]>(){ @Override public int compare(long[] a,long[] b){ int tmp=a[0]!=b[0]?1:-1; if(tmp==1) return (int)(a[0]-b[0]); return (int)(a[1]-b[1]); } }); //记录每个会议室被预定的次数，(索引->会议室编号,值->次数) int[] count =new int[n]; //按顺序处理每一场会议 for(int[] t:m){ long start=t[0]; long end=t[1]; //释放当前会议开始前已经结束的会议室 //把结束时间<=当前会议开始时间的会议室放回空闲队列 while(!using.isEmpty()&&using.peek()[0]<=start){ //弹出已结束的会议室，获取其编号并加入空闲队列 int roomid=(int)using.poll()[1]; id.offer(roomid); } int assign;//分配给当前会议的会议室编号 //情况1：有空闲会议室 if(!id.isEmpty()) assign=id.poll(); //情况2：无空闲会议室->等待最早结束的会议室释放 else{ long[] early=using.poll();//弹出最早结束的会议室信息 long endtime=early[0];//该会议室的结束时间 int roomid=(int)early[1];//该会议室的编号 //当前会议需要延时开始，结束时间也同步延 //延后时长=会议室结束时间-当前会议原开始时间 end=end+(endtime-start); assign=roomid;//分配这个刚释放的会议室 } //将当前会议的结束时间和分配的会议室编号加入正在使用的队列 using.offer(new long[]{end,assign}); //该会议室的预定次数+1 count[assign]++; } //找出预定次数最多的会议室，次数相同选编号最小的 int ret=0; for(int i=0;i<n;i++) if(count[i]>count[ret]) ret=i; return ret; } }