题目
给你一个会议时间安排的数组 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^4
0 <= 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;
}
}
评论区