【堆】leetcode253.会议室II_leetcode 会议室 python

题目：
给你一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，返回 所需会议室的最小数量 。

思路：
开始时，按会议开始时间进行排序（先开始的会议需要先安排）。
需要使用小根堆，来记录当前会议的最早结束时间（以判别当前是否有空闲会议室可用）

解答：

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        res=1
        #1.按照会议开始时间进行排序
        intervals.sort(key=lambda x:x[0])
        #print(intervals)
          #堆中只需记录会议的结束时间，以判别当前是否有可用的空会议室
        heap=[]
        heapq.heappush(heap,intervals[0][1])
        n=len(intervals)
        for i in range(1,n):
            #对每个会议，检查堆的最小元素（即堆顶部的房间）是否空闲。
            #若空闲无需新增房间,则更新会议结束时间
            if heap[0]<=intervals[i][0]:
                heapq.heappop(heap)
            #无空闲，需新增房间
            else:
                res+=1
            heapq.heappush(heap,intervals[i][1])
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

方法二：

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        #1.按照会议开始时间进行排序
        intervals.sort(key=lambda x:x[0])
        #print(intervals)
          #堆中只需记录会议的结束时间，以判别当前是否有可用的空会议室
        heap=[]
        heapq.heappush(heap,intervals[0][1])
        n=len(intervals)
        for i in range(1,n):
            #对每个会议，检查堆的最小元素（即堆顶部的房间）是否空闲。
            #若空闲无需新增房间,则更新会议结束时间
            if heap[0]<=intervals[i][0]:
                heapq.heappop(heap)
            heapq.heappush(heap,intervals[i][1])
        return len(heap)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16