题目

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

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

示例 2:
输入: [[7, 10], [2, 4]]
输出: 1

方案一

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        # 1. 将 intervals 按照地一个值进行排序
        # 2. 每个会议室维护一个最晚结束的时间点
        # 3. 遍历 intervals，根据能否在该会议室安排确定是否要更新最晚结束时间
        intervals.sort()
        rooms = [] # 每个 room 的最晚结束时间
        for interval in intervals:
            start, end = interval
            for i, room in enumerate(rooms):
                if room <= start: # 可以继续安排新的会议
                    rooms[i] = end
                    break
            else: # 没有找到合适的会议室
                rooms.append(end)
        return len(rooms)

时间复杂度
方案二（最小堆）
```python import heapq

class Solution: def minMeetingRooms(self, intervals: [[int]]) -> int: rooms = [0] # rooms 堆，一开始有一个会议室 intervals.sort() for interval in intervals: start, end = interval

        min_endtime = rooms[0]  # 所有会议室的最小结束时间
        if min_endtime <= start:  # 可以安排新的会议
            heapq.heapreplace(rooms, end)
        else:
            heapq.heappush(rooms, end)
    return len(rooms) if rooms[0] != 0 else 0


- 使用最小堆来减少方案一寻找 room 的时间复杂度
<a name="WRcfc"></a>
# 方案三（堆）
```go
func minMeetingRooms(intervals [][]int) int {
    h := &Heap{}
    for _, interval := range intervals {
        heap.Push(h, interval)
    }

    // rooms 维护每个会议室会议结束的时间
    rooms := []int{0}
    outer:
    for h.Len() > 0 {
        interval := heap.Pop(h).([]int)
        for i, eTime := range rooms {
            // 开始时间比较晚，不需要新的会议室了
            if interval[0] >= eTime {
                rooms[i] = interval[1]
                continue outer
            }
        }

        rooms = append(rooms, interval[1])
    }

    return len(rooms)
}

type Heap [][]int

func (h Heap) Len() int           { return len(h) }
func (h Heap) Less(i, j int) bool { return h[i][0] < h[j][0] }
func (h Heap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *Heap) Push(x interface{}) {
    *h = append(*h, x.([]int))
}

func (h *Heap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

参考地址

https://leetcode-cn.com/explore/featured/card/2020-top-interview-questions/283/heap-stack/1267/
https://leetcode-cn.com/problems/meeting-rooms-ii/solution/hui-yi-shi-ii-by-leetcode/
https://leetcode-cn.com/problems/meeting-rooms-ii/

算法（leetcode）

253. 会议室 II

题目

方案一

方案二（最小堆）

参考地址