【进阶篇】堆

[azl397985856]

由于堆在力扣中常常用于模拟题目，因此这里给大家留一个模拟的题目。 这道题目比一般的堆模拟难度要稍微大一点。 6170. 会议室 III

[azl397985856]

和一般堆模拟类似， 只不过这道题不仅

• 对空闲的会议室要堆化处理。对应题目的 "每场会议都会在未占用且编号 最小 的会议室举办。"

• 还要对正在使用的会议室进行堆处理。对应题目的 “如果没有可用的会议室，会议将会延期，直到存在空闲的会议室。”

代码

class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        h = [i for i in range(n)]
        busy = []
        meetings.sort()
        counts = [0] * n
        for s, e in meetings:
            while busy and busy[0][0] <= s:
                heapq.heappush(h, heapq.heappop(busy)[1])
            if h:
                i = heapq.heappop(h)
                heapq.heappush(busy, (e, i))
            else:
                end, i = heapq.heappop(busy)
                heapq.heappush(busy, (end - s + e, i))
            counts[i] += 1
            
        max_v = max(counts)
        for i, count in enumerate(counts):
            if count == max_v: return i