X

LEETCODE 253. Meeting Rooms II 解题思路分析

题目大意:

会议室 II

给定一个会议时间安排的数组,每个会议时间都会包括开始和结束的时间 [[s1,e1],[s2,e2],...] (si < ei),为避免会议冲突,同时要考虑充分利用会议室资源,请你计算至少需要多少间会议室,才能满足这些会议安排。

示例 1:

输入: [[0, 30],[5, 10],[15, 20]]
输出: 2

示例2:

输入: [[7,10],[2,4]]
输出: 1

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=253

解题思路分析:

本题求需要的最少的会议室数量,其实是求同一时间点最多有多少个会议在召开,这些在某一时间点同时进行的会议是不能使用相同会议室的。因此最大同时召开会议的个数即是本题的解。

解题时,需要先按照会议的开始时间升序排序一下数组,然后建立一个Queue,升序保存先于自身开始的会议的结束时间。循环遍历每个会议的时间段,对于任意一个当前会议,是否需要增加一间新的会议室取决于早于它开始的其他会议是否已经结束。因此,我们先查看Queue中其他会议的结束时间是否小于等于当前会议的开始时间,将相比于当前会议开始时间点已经结束的会议从Queue中删除,然后再将当前会议的结束时间加入到Queue中。此时Queue中保存的会议应该是在同时进行且还没有结束的所有会议,因此Queue的元素个数即是我们在此刻需要的最少会议室个数,用该个数更新全局结果的最大值。直到循环结束,返回全局最大值即可。

实现代码:

public int minMeetingRooms(int[][] intervals) {
    // 如果没有会议,返回0
    if(intervals.length==0) return 0;
    // 按照开始时间排序数组
    Arrays.sort(intervals, (a,b)->a[0]-b[0]);
    // 定义一个Queue,保存正在进行会议的结束时间
    PriorityQueue<Integer> q = new PriorityQueue<>();
    // 返回结果
    int max=1;
    // 循环遍历每一个会议
    for(int[] in:intervals){
        // 如果当前会议的开始时间大于等于Queue中会议的结束时间
        while(q.size()>0&&in[0]>=q.peek()){
            // 删除掉已经结束的会议
            q.poll();
        }
        // 将当前会议的结束时间加入Queue
        q.offer(in[1]);
        // 当前同时进行的会议个数为需要会议室的数量
        max=Math.max(max, q.size());
    }
    return max;
}

本题解法执行时间为9ms。

Runtime: 9 ms, faster than 45.13% of Java online submissions for Meeting Rooms II.

Memory Usage: 46.9 MB, less than 5.12% of Java online submissions for Meeting Rooms II.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-253-meeting-rooms-ii-解题思路分析/
Categories: leetcode
kwantong: