【Leetcode】堆系列

【Leetcode-253】

一、题目：会议室2

　　给你一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，为避免会议冲突，同时要考虑充分利用会议室资源，请你计算至少需要多少间会议室，才能满足这些会议安排。

二、代码：

def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        """
        思路：对开始时间排序，对每一项，找是否有空闲房间，没有的话开一个。用结束时间的最小堆找是否冲突，如果不冲突把房间结束时间替换掉，否则加入。即，假设每次会议都要新开房间，但与最早结束时间不冲突时可以抢占原来的房间。
        """
        intervals.sort(key=lambda x: x[0])
        heap = []
        heapq.heappush(heap, intervals[0][1])
        for item in intervals[1:]:
            if heap[0] <= item[0]:  # 不冲突
                heapq.heappop(heap)
            heapq.heappush(heap, item[1])
        return len(heap)

博文转载请注明出处。