聖地亞歌

Leetcode P0253"Meeting Rooms II" 题解

2021/04/10 Leetcode

博文中会简要介绍Leetcode P0253题目分析及解题思路。

“Meeting Rooms II”是一道中等难度的题目，是p0252的衍生题。基本思路是结合贪心算法和最小堆来解决。

Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2

基于开始时间排序的贪心算法思路基本与p0252一致，这里不再赘述。

这道题要求得到容纳全部会议所需要的最少会议室数目。显然，一个会议室能否被两个会议共用，取决于给定的试图使用该会议室的两个会议是否重叠。如果重叠，那么这个会议室就不能被这两个会议共用，否则，可以被共用。

如何得到可以与当前会议共用会议室的会议？

我们可以通过维护一个最小堆来存储所有会议室信息。这个最小堆中存储了所有会议室的最晚的使用结束时间，则如果堆顶的会议室的最晚会议结束时间早于当前会议的开始时间，则当前会议可以共用堆顶的这个会议室。

同时我们也需要更新这个会议室最后被使用的结束时间，因为存在共用，那么一个会议室的使用结束时间不再取决于单个会议的结束时间，而取决于共用这个会议室的所有会议中最后一个使用它的会议的结束时间，既然当前会议共用了这个会议室，那么这个会议室的使用结束时间就等于当前会议的结束时间，此时更新结束。

为什么一定选择最小堆堆顶的会议室来共用？

其实，在使用最小堆时，我们同样也用到了贪心策略，即贪婪地选取最早结束的会议室。我们可以简单地论证贪心策略在这里的正确性。

我们选取两个会议室的结束时间t1和t2，同时我们现在需要为会议m1选择一个会议室，且m1[0] >= max(t1, t2)。不失一般性地，我们假定t1是最早结束，t2是次早结束，若m1选择t2会议室且能得到最优解，此时假设存在一个会议m2，可以和m1共用会议室，由于t1的结束时间更早，那么为m1选择t1一定也能使得m2能够与m1共用会议室，即选择t1一定能得到最优解。

也就是说，若存在其他最优解，“每次选择最早结束的会议室”得到的解一定能不差于最优解。于是我们可以贪婪地选取最早结束的会议室来得到最优解。

以下是Java的题解代码实现。

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        Arrays.sort(intervals, (x, y) -> {
            return (x[0]-y[0]);
        });
        
        // Record the earliest available meeting room
        Queue<Integer> minHeap = new PriorityQueue<>();
        minHeap.offer(0);
        // Record the total required number of rooms
        int rooms = 1;
        for (int[] interval: intervals) {
            int start = interval[0], end = interval[1];
            if (start < minHeap.peek()) {
                ++rooms;
            }
            else {
                minHeap.poll();
            }
            
            minHeap.offer(end);
        }
        
        return rooms;
    }
}

以下是C++的题解代码实现。

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](vector<int> x, vector<int> y) {
            if (x[0] <= y[0])
                return true;
            else 
                return false;
        });
        
        priority_queue<int, vector<int>, greater<int>> min_heap;
        min_heap.push(0);
        int rooms = 1;
        for (vector<int> interval: intervals) {
            int start = interval[0], end = interval[1];
            if (start < min_heap.top()) {
                ++rooms;
            }
            else {
                min_heap.pop();
            }
            
            min_heap.push(end);
        }
        
        return rooms;
    }
};

Search

    Table of Contents