越而胜己 / Beyond awesome

Link to problem: https://leetcode.com/problems/meeting-rooms-ii/

This is a classic application of interval partitioning, which is realized using a greedy algorithm: we sort the meetings by their starting time, and greedily allocate rooms for the meetings. If a meeting can be arranged in a room that already exists, we arrange it there so we don’t have to allocate a new room; if a meeting overlaps with other meetings such that there is no room available, we allocate another room.

When deciding whether there is a room available for room (s,t), we can try to find if there exists a room whose last meeting ends before s, i.e. if the first meeting room that becomes available is available before time s. To find the first meeting room that becomes available, we use a heap to store the time when the meeting rooms become available.

Using a heap costs us $\O(n)$ space. The time complexity is $\O(n \log n)$, because we need to update the heap for every meeting that we greedily process.

这是 interval partitioning 的经典应用,解法是使用贪心算法:将所有会议按照开始时间排序后,逐个安排房间。如果一个会议可以安排在已经存在的房间,则就安排在已存在的房间进行;如果遇到时间重叠无法安排的会议,则需要分配一个新的房间。

判断会议 (s,t) 是否有可用的房间时,我们可以查找是否有最后一个会议结束时间早于 s 的会议室,即当前最早空出来的会议室是否早于 s 空出来。为了快速找到最早空出来的会议室,我们可以使用一个堆来存储所有会议室空出来的时间。

使用堆需要 $\O(n)$ 的额外空间。时间复杂度则是 $\O(n \log n)$,因为我们处理每个会议时都需要更新堆。

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        
        free_rooms = []
        intervals.sort(key=lambda x:x[0])
        
        heapq.heappush(free_rooms, intervals[0][1])
        
        for i in intervals[1:]:
            if free_rooms[0] <= i[0]:
                heapq.heappop(free_rooms)
            heapq.heappush(free_rooms, i[1])
            
        return len(free_rooms)