leetcoe253 最少会议室问题

秒速五厘米 2022-09-11 00:04 160阅读 0赞

题目：有一堆会议，每个会议都有开始时间和结束时间，问至少需要几个房间可以安排下这些会议？

该问题可以使用贪心来做，使用小顶堆来实现最简单。  
首先用一个最小堆来将会议按照会议开始时间从小到大排序，  
然后遍历该小顶堆。  
在遍历里面，如果第二个小顶堆不为空，并且第二个小顶堆的堆顶值小于等于遍历出堆的开始值，就将堆顶值出堆，然后将该会议的结束时间入堆。  
否则将堆的结束时间入最小堆。  
最后第二个堆的大小就是最少会议室数量。看代码可能更好理解。

package BiShi;
    import java.util.PriorityQueue;
    public class HuiYiShi {
        
        public static int getNum(int[][] arr){
        
            //里面节点的数量就是会议室的数量，里面存每个会议室使用的最迟的结束时间
            PriorityQueue<Integer> queue=new PriorityQueue<>((a,b)->(a-b));
            //按照会议开始时间排序，里面存arr数组的下标，
            PriorityQueue<Integer> queue1=new PriorityQueue<>((a,b)->(arr[a][0]-arr[b][0]));
            for(int i=0;i<arr.length;i++){
        
                queue1.offer(i);
            }
            while(!queue1.isEmpty()){
        
                if(!queue.isEmpty()&&queue.peek()<=arr[queue1.peek()][0]){
        
                    //判断结束时间最小的会议室是否能续用，能就将原该会议室结束时间出堆，然后将新的结束时间入堆
                    queue.poll();
                    queue.offer(arr[queue1.poll()][1]);
                }else{
        
                    //否则就开一个新的会议室
                    queue.offer(arr[queue1.poll()][1]);
                }
            }
            return queue.size();
        }
        public static void main(String[] args) {
        
            int[][] arr=new int[][]{
        {
        6,7},{
        4,5},{
        5,6},{
        2,6}};
            int res= HuiYiShi.getNum(arr);
            System.out.println(res);
        }
    }