leetcode253. 会议室II(java)：最小堆

题目

思路
用优先队列实现最小堆
1.先将数组进行升序排序

 Arrays.sort(intervals,(o1,o2)->o1[0]-o2[0]);

这里使用了Lambda表达式，完整写法应该是

Arrays.sort(intervals,new Comparator<int[]>(){
	@Override
	public int compare(int[]o1,int[]o2){
		return o1[0]-o2[0];
	}
});

o1[0]-o2[0] <=0，且o1排在o2前面，所以是升序排序。
3.将会议的结束时间存入优先队列（升序排序），队首元素为最早会议结束时间(start)，如果另一场会议的开始时间早于start，则没有空闲会议室，需要新开一间；否则，弹出队首元素。
4.最后队列中的剩余元素为会议室数量

具体代码

import java.util.LinkedList;
class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if(intervals == null || intervals.length == 0){
            return 0;
        }
        Arrays.sort(intervals,(o1,o2)->o1[0]-o2[0]);
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1,o2)->o1-o2);
        queue.offer(intervals[0][1]);
        for(int i = 1;i < intervals.length;i++){
            if(intervals[i][0]>=queue.peek()){
                queue.poll();
            }
            queue.offer(intervals[i][1]);
        }
        return queue.size();
    }
}

时间复杂度：
排序：O(NlogN)；插入和删除：O(logN)
所以总的时间复杂度为O(NlogN)
空间复杂度： O(N)

最后

以上就是饱满咖啡豆为你收集整理的leetcode253. 会议室II(java)：最小堆的全部内容，希望文章能够帮你解决leetcode253. 会议室II(java)：最小堆所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。