# LC253. Meeting Rooms II

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)
```