LeetCode 热题 HOT 100 第六十三天 253. 会议室 II 中等题 用python3求解_leetcode 会议室 python

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

示例 1：
输入：intervals = [[0,30],[5,10],[15,20]]
输出：2

示例 2：
输入：intervals = [[7,10],[2,4]]
输出：1

提示：
1 <= intervals.length <= 104
0 <= starti < endi <= 106

解法：排序 + 优先队列（最小堆）

思路：
假设一开始一个会议室都没开放，且会议室开放后不会关闭，可以重复使用。

按照我们日常的逻辑，先对所有的会议安排按照开始时间升序排列。

安排第一个会议，此时一个会议室都没有，直接开放一间会议室使用；安排第 i 个会议，查看当前有没有会议室是已开放且空闲的，没有则接着开放新的会议室；

查看是否有会议室已开放且空闲，是看当前正在使用会议室的会议中，最早结束的那场会议的结束时间，如果现在还没结束，说明其他会议更不可能结束，直接开放新的会议室。

若在以开放的会议室中，最早结束的那场会议已经结束，说明现在存在空闲会议室，直接加入即可。

步骤：
1.先对所有的会议时间按开始时间从小到大排序。

intervals.sort()
1

2.接着定义一个小顶堆作为会议室，每个节点的值是会议的结束时间。

3.小顶堆在我的代码中是用优先队列。无论加入多少个队列，小顶堆的堆顶就是当前使用会议室中最早的结束时间，并且小顶堆的元素个数即会议室当前占用的间数。

4.最早开始的会议的结束时间 add 到小顶堆中。

5.接着对 [1, size-1] 个会议依次进行以下操作：

5.1.对比当前会议的开始时间和小顶堆的堆顶元素值，若小于，说明当前所有会议室正在进行的会议中，最早结束的都还没结束，只能新建会议室了；

heapq.heappush(heap, right)
1

5.2.若当前会议的开始时间大于小顶堆的堆顶元素值，说明会议室正在进行的会议中，最早结束的会议已经结束，可以把它从小顶堆删除，自己进入小顶堆（重复利用会议室）。

while heap and heap[0] <= left:
    heapq.heappop(heap)
1
2

5.3.等最后一个会议时间进入小顶堆，此时的小顶堆元素个数即至少需要的会议室数量。

代码实现：

import heapq # heapq库中的堆默认是最小堆(树中各个父节点的值总是小于或等于任何一个子节点的值)
def minMeetingRooms(intervals):
    intervals.sort() # 按开始时间排序(按各数组的第一个元素大小排序)
    heap = []  # 结束时间堆
    ans = 0
    for interval in intervals:
        left, right = interval # 如interval:[0,30]，则left:0;right:30
        while heap and heap[0] <= left: # heap[0]是堆中的最小值
            heapq.heappop(heap) # 弹出堆heap中最小值(删除并返回最小值，因为堆的特征是heap[0]永远是最小的元素，所以一般都是删除第一个元素)
        heapq.heappush(heap, right) # 把元素right加入堆heap中
        ans = max(ans, len(heap))
    return ans
1
2
3
4
5
6
7
8
9
10
11
12

注意：heapq堆数据结构最重要的特征是heap[0]永远是最小的元素