会议室 II 图解题解

本质是求最大重叠数

如果某一时刻有 k 场会议同时进行，少于 k 间会议室一定不够；反过来，只要每场开始前复用所有已经空出的房间，峰值为 k 时就总能用 k 间完成安排。因此最少房间数等于时间线上的最大并发会议数。

这解释了为什么不能只看最后还剩多少场：高峰可能出现在中间，后面的会议变少并不会降低曾经必须准备的房间数。

最小堆维护当前活跃会议

先按 start 升序处理会议。堆里只存尚未结束会议的 end，堆顶是最早结束时间。处理 [start,end] 前，只要 heap[0]≤start，就说明该会议已结束，应继续弹出。

释放完成后压入 end。此时堆中每个元素都对应 start 时刻仍在进行的一场会议，因此堆大小具有明确含义：当前真实并发数。用 best 取全程最大值即可。

为什么必须是 while，而不是 if

相邻两次开始之间可能结束多场会议。例如活跃结束时间是 [18,20,30,35]，新会议从 25 开始，18 和 20 都已经结束。若只弹一次，20 会错误残留在堆里，堆大小就不再等于当前并发。

经典的“只弹一个、最终返回堆大小”写法也可以求最少房间数，但那时堆表示已分配房间的最新结束时间集合，而不是当前活跃会议。教学中不能把两套语义混在一起。

正确性与端点约定

按开始时间推进时，while 会恰好删除所有在当前开始时间之前或同时结束的会议，留下的会议都与当前会议重叠。加入当前会议后，堆大小因此等于该时刻需要的房间数；best 覆盖所有开始时刻，也就覆盖全部可能出现新峰值的时刻。

释放条件必须是 end≤start。会议 [0,10] 与 [10,20] 首尾相接，不发生重叠，可以使用同一间房；写成 end<start 会多算一间。

复杂度与扫描线替代方案

排序需要 O(n log n)。每个结束时间最多入堆一次、出堆一次，每次 O(log n)，总时间仍为 O(n log n)；最坏全部重叠时堆空间 O(n)。

另一种做法是分别排序 start 与 end，用双指针维护当前并发和峰值。它同样是 O(n log n)，更像扫描线；堆写法则更直观地展示哪些会议仍活跃，也更容易扩展到房间分配明细。

Python

import heapq
class Solution:
    def minMeetingRooms(self, intervals):
        if not intervals: return 0
        intervals.sort(key=lambda x: x[0])   # 按开始时间排序
        heap = []                            # 存各房间的结束时间（最小堆）
        for s, e in intervals:
            if heap and heap[0] <= s:        # 最早空出的房间已散
                heapq.heappop(heap)          # 复用：腾出它
            heapq.heappush(heap, e)          # 占用到 e
        return len(heap)                     # 堆大小的峰值 = 最少房间数

Java

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if (intervals.length == 0) return 0;
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);  // 按开始时间排序
        PriorityQueue<Integer> heap = new PriorityQueue<>();  // 最小堆：结束时间
        for (int[] it : intervals) {
            if (!heap.isEmpty() && heap.peek() <= it[0])  // 最早空出的房间已散
                heap.poll();                 // 复用：腾出它
            heap.offer(it[1]);               // 占用到结束时间
        }
        return heap.size();                  // 堆大小的峰值 = 最少房间数
    }
}

C++

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        if (intervals.empty()) return 0;
        sort(intervals.begin(), intervals.end());  // 按开始时间排序
        priority_queue<int, vector<int>, greater<int>> heap;  // 最小堆
        for (auto& it : intervals) {
            if (!heap.empty() && heap.top() <= it[0])  // 最早空出的房间已散
                heap.pop();                  // 复用：腾出它
            heap.push(it[1]);                // 占用到结束时间
        }
        return heap.size();                  // 堆大小的峰值 = 最少房间数
    }
};