难度: Medium
Submission
运行时间: 27 ms
内存: 18.5 MB
class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
intervals.sort()
pq = []
ans = 0
for a in intervals:
while pq and pq[0] <= a[0]:
heapq.heappop(pq)
heapq.heappush(pq, a[1])
ans = max(ans, len(pq))
return ans
Explain
这个题解是使用优先队列（小根堆）来解决会议室安排问题。首先对会议时间区间按开始时间排序。然后遍历每个会议，对于当前遍历到的会议，如果优先队列不为空且队首元素小于等于当前会议的开始时间，说明队首的会议已经结束，可以弹出队首。接着将当前会议的结束时间加入优先队列。同时维护一个变量 ans 记录优先队列的最大长度，即需要的最多会议室数量。最后返回 ans 即可。
时间复杂度: O(nlogn)
空间复杂度: O(n)
class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
intervals.sort() # 按会议开始时间排序
pq = [] # 存储会议结束时间的最小堆
ans = 0 # 记录所需的最多会议室数
for a in intervals:
while pq and pq[0] <= a[0]: # 当最小堆非空且堆顶元素小于等于当前会议开始时间
heapq.heappop(pq) # 弹出堆顶元素，即最早结束的会议
heapq.heappush(pq, a[1]) # 将当前会议的结束时间加入最小堆
ans = max(ans, len(pq)) # 更新所需的最多会议室数
return ans
Explore
这行代码是关键部分，它确保了能够正确地计算出在任何时刻所需的最大会议室数量。优先队列（小根堆）`pq`用于存储各个会议的结束时间。每次将一个会议的结束时间加入到堆中，堆的大小（即`len(pq)`）就代表了此时正在进行中的会议数量。因此，每次在添加一个新的会议结束时间后，堆的大小就是当前需要的会议室数量。`ans = max(ans, len(pq))`这行代码在每次会议加入后执行，用来更新所需会议室的最大数量。如果当前的堆大小（正在进行的会议数量）比之前记录的`ans`大，那么更新`ans`为当前的堆大小。这样一来，遍历所有会议后，`ans`中存储的就是在任何时刻所需的最大会议室数量。