侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【贪心算法, 优先队列, 差分数组】会议室 II

GabrielxD
2022-05-25 / 0 评论 / 0 点赞 / 46 阅读 / 1,092 字 / 正在检测是否收录...

题目

253. 会议室 II

6178. 将区间分为最少组数


给你一个会议时间安排的数组 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]] 为例:

image-20220525151006986

只需要把所有时间区分好开始还是结束,放入一个优先队列中,然后从优先队列中取出时间,如果当前时间表示会议开始则 count++ 如果会议结束则 count-- 维护一个 ans 记录最大的 count 即是所需最少的办公室数量。

但是需要注意这种情况:[[2,11], [6,16], [11,16]]

image-20220525152918080

如上图的理解就是错误的,因为 11 只是一个时间点,在 [2, 11] 这个会议结束的时候完全可以让 [11, 16] 会议使用原会议室续上,而不是新开一个会议室

正确的理解应该是这样:

image-20220525153234959

由此可得,优先队列的排序条件应该是:

  • 按照时间升序排序。
  • 如果时间相同,则结束时间应该排在开始时间的前面。

代码

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;
    }
}
0

评论区