题目
给你一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [start_i, end_i] ，返回 所需会议室的最小数量 。
示例 1：
输入：intervals = [[0,30],[5,10],[15,20]]
输出：2
示例 2：
输入：intervals = [[7,10],[2,4]]
输出：1
提示：
1 <= intervals.length <= 10^40 <= start_i < end_i <= 10^6
解题
方法一：优先队列
思路
不区分是哪个区间在开始会议或者结束会议，只需要注意什么时候是开始会议，什么时候是结束会议即可。
以 [[0,30], [5,10], [15,20]] 为例：
只需要把所有时间区分好开始还是结束，放入一个优先队列中，然后从优先队列中取出时间，如果当前时间表示会议开始则 count++ 如果会议结束则 count-- 维护一个 ans 记录最大的 count 即是所需最少的办公室数量。
但是需要注意这种情况：[[2,11], [6,16], [11,16]]
如上图的理解就是错误的，因为 11 只是一个时间点，在 [2, 11] 这个会议结束的时候完全可以让 [11, 16] 会议使用原会议室续上，而不是新开一个会议室。
正确的理解应该是这样：
由此可得，优先队列的排序条件应该是：
- 按照时间升序排序。
- 如果时间相同，则结束时间应该排在开始时间的前面。
代码
class Solution {
public int minMeetingRooms(int[][] intervals) {
int len = intervals.length;
Queue<int[]> queue = new PriorityQueue<>((a, b) ->
a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
// 队列中元素: item[0]表示时间 item[1]如果是0表示开始而如果是1表示结束
for (int[] interval : intervals) {
queue.offer(new int[]{interval[0], 0});
queue.offer(new int[]{interval[1], 1});
}
int ans = 1, count = 0;
while (!queue.isEmpty()) {
int[] curr = queue.poll();
if (curr[1] == 0) count++;
else count--;
ans = Math.max(ans, count);
}
return ans;
}
}
优化
由于优先队列只是拿来排了个序，而且其初始化大小其实是已知的，完全可以拿一个数组来代替它：
class Solution {
public int minMeetingRooms(int[][] intervals) {
int len = intervals.length;
int[][] helper = new int[len * 2][2];
int idx = 0;
for (int[] interval : intervals) {
helper[idx][0] = interval[0];
helper[idx++][1] = 0;
helper[idx][0] = interval[1];
helper[idx++][1] = 1;
}
Arrays.sort(helper, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
int ans = 1, count = 0;
for (int[] curr : helper) {
if (curr[1] == 0) count++;
else count--;
ans = Math.max(ans, count);
}
return ans;
}
}
方法二：优先队列
思路
按开始时间升序对会议数组进行排序，建立一个优先队列，里面只用存结束时间，先把第一个会议(开始最早的)的结束时间入队，然后从第二个会议开始遍历数组，对于遍历到的每个会议：
- 如果当前会议的开始时间大于等于队列头部(最小)的结束时间的话，队列头部的会议可以就可以为当前会议腾出会议室，把队列顶部会议出队，然后把当前会议的结束时间入队。
- 否则说明没有正在进行中的会议可以为当前会议腾出会议室，故需要一个新的会议室，直接把当前会议的结束时间入队即可。
最后直接返回队列剩下中的元素个数（因为从始至终队列中都只少了那些腾出了会议室的会议）。
代码
class Solution {
public int minMeetingRooms(int[][] intervals) {
int len = intervals.length;
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
Queue<Integer> queue = new PriorityQueue<>();
queue.offer(intervals[0][1]);
for (int i = 1; i < len; i++) {
int[] curr = intervals[i];
if (curr[0] >= queue.peek()) queue.poll();
queue.offer(curr[1]);
}
return queue.size();
}
}
方法三：差分数组
思路
具体思路见【贪心算法, 优先队列, 差分数组】将区间分为最少组数【力扣第 310 场周赛】
代码
class Solution {
static final int N = (int) 1e6 + 10;
public int minMeetingRooms(int[][] intervals) {
int[] diffs = new int[N];
for (int[] interval : intervals) {
++diffs[interval[0]];
--diffs[interval[1]];
}
int height = 0, cnt = 1;
for (int diff : diffs) {
height += diff;
if (height > cnt) cnt = height;
}
return cnt;
}
}
评论区