一刷185-力扣热题-253会议室II（m）_力扣253

题目：
给定一个会议时间安排的数组，
每个会议时间都会包括开始和结束的时间 [[s1,e1],[s2,e2],…] (si < ei)，
为避免会议冲突，同时要考虑充分利用会议室资源，请你计算至少需要多少间会议室，才能满足这些会议安排。
示例：
输入: [[0, 30],[5, 10],[15, 20]]
输出: 2

输入: [[7,10],[2,4]]
输出: 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前面，所以是升序排序。

将会议的结束时间存入优先队列（升序排序），队首元素为最早会议结束时间(start)，
如果另一场会议的开始时间早于start，则没有空闲会议室，需要新开一间；否则，弹出队首元素。

最后队列中的剩余元素为会议室数量

时间复杂度：
排序：O(NlogN)；插入和删除：O(logN)
所以总的时间复杂度为O(NlogN)
空间复杂度： O(N)
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++) {//从第二个会议开始遍历
			//若之后的会议开始时间 大于 当前栈中栈顶存储的结束时间 
			//（大于: 会议开始时间 在 栈顶时间之后）  
			//弹栈：代表 这个会议室可以重复使用， 不需要重新开新的一间会议室 所以queue--
			if (intervals[i][0] >= queue.peek()) {
				queue.poll();
			}
			queue.offer(intervals[i][1]); 
		}
		return queue.size();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

（plus题目）