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

题目地址
给你一个会议时间安排的数组 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
LeetCode 热题 HOT 100 第六十三天 253. 会议室 II 中等题 用python3求解_第1张图片
解法:排序 + 优先队列(最小堆)
LeetCode 热题 HOT 100 第六十三天 253. 会议室 II 中等题 用python3求解_第2张图片
思路:
假设一开始一个会议室都没开放,且会议室开放后不会关闭,可以重复使用。

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

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

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

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

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

intervals.sort()

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

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

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

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

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

heapq.heappush(heap, right)

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

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

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

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

你可能感兴趣的