力扣 253. 会议室II

由于是会员题目，这里对题目进行描述

题目描述

给定一个会议时间安排的数组，每个会议时间都会包括开始和结束的时间[[s1, e1], [s2,e2], …](si < ei)，为避免会议冲突，同时要考虑充分利用会议室资源，请你计算至少需要多少间会议室，才能满足这些会议安排？

示例1：
input： [[0, 30], [5, 10], [15, 20]]
output：2

示例2：
input： [[7, 10], [2, 4]]
output：1

思路1 优先队列

1. 按照开始时间对会议进行排序。
2. 以会议结束时间构建最小堆，判断是否有会议室空着可使用。
3. 1. 如果空闲，直接开始会议
   2. 如果不空闲，开新房间，加入堆

解法1

import heapq
def minMeetingRooms(intervals):
    if not intervals: return 0
    # 堆
    intervals.sort(key=lambda x: x[0])
    heap = []
    for inter in intervals:
        if heap and heap[0] <= inter[0]:
            heapq.heappop(heap)
        heapq.heappush(heap, inter[1])

    return len(heap)

思路2 双指针

1. 分别按照开始时间和结束时间对会议进行排序。
2. 双指针分别指向开始和结束
3. 会议室会随着开始指针右移一直增加，但如果开始指针大于等于结束指针，会议室数量-1，结束指针后移1位

解法2

def minMeetingRooms(intervals):
    if not intervals: return 0
    # 双指针
    start, end = [], []
    for inter in intervals:
        start.append(inter[0])
        end.append(inter[1])
    start.sort()
    end.sort()
    left, right, ret = 0, 0, 0
    while left < len(intervals) and right < len(intervals):
        if start[left] >= end[right]:
            right += 1
            ret -= 1
        ret += 1
        left += 1
    return ret