会议室 II 图解题解

会议室 II 求的到底是什么

给一组会议的开始、结束时间，问最少要几间会议室才能让所有会议互不冲突。换个说法：在时间轴上，这些区间最多有几个同时叠在一起——重叠的会议必须各占一间，所以答案就是「最大同时重叠数」。抓住这层抽象，这道题就从会议室推广到一切「同时抢资源」的调度问题：站台数、服务器并发数，本质都一样。

为什么会议室 II 想到用最小堆

直觉的贪心是：会议按开始时间排好序逐场安排，能塞进已有房间就复用，实在不行才新开一间。这个贪心的关键子问题是——当前会议开始时，有没有房间已经空出来了？逐间检查所有房间要 O(n)，太慢。

观察到只需要问一间房：所有占用中的房间里「最早结束」的那间。它都还没散会，其他房间更没散，必须新开；它散了，就复用它。「反复取最小值、且元素动态进出」正是最小堆（优先队列）的看家本领：堆顶永远是最小值，插入删除都只动一条路径，各 O(log n)。于是把每间房的结束时间丢进最小堆，堆顶就是那间最早空出的房。

每一步的复用与新开为什么都对

会议 [s, e] 到来时比较堆顶：heap[0] ≤ s，说明最早散会的房间在这场会开始前（或恰好在开始那一刻）已腾出，弹出堆顶再压入 e——一出一进，堆大小不变，对应「复用」；heap[0] > s，说明现有房间全在忙，直接压入 e，堆大小加一，对应「新开一间」。注意相接不算冲突：上一场 10 点结束、这一场 10 点开始，同一间房接得上，所以判断带等号。

堆大小只在「所有房都忙」时才增长，而那一刻的堆大小恰好等于当时同时进行的会议数。又因为按开始时间排序，每场会议在它开始的时刻被处理，重叠计数不会漏算。所以最终的堆大小 = 过程中同时占用的峰值 = 最少会议室数，参考代码最后直接 return len(heap)。

不用堆的扫描线解法是什么关系

把每场会议拆成两个事件：开始时刻 +1、结束时刻 -1，全部事件按时间排序后扫一遍，计数器的历史最大值就是答案，这就是扫描线做法，同样 O(n log n)。它和堆解殊途同归：都在数「最大同时重叠」，堆解用堆的实时大小当计数器，扫描线用显式加减。面试里能把两种解法的等价性讲清楚，是很好的加分点。

复杂度与最容易错的三个点

时间 O(n log n)：排序 O(n log n)，之后每场会议至多一次弹出、一次压入，各 O(log n)。空间 O(n)：最坏所有会议全部重叠，堆里同时装下 n 个结束时间。

三个高频错误：一是往堆里存开始时间——要判断的是「房间何时空出」，必须存结束时间；二是把答案理解成「扫完后还剩几间在用」，其实要的是过程中的峰值（本解法堆大小不会缩，天然记住了峰值）；三是把端点相接当成冲突，漏掉 heap[0] ≤ s 里的等号，会多开无谓的房间。

Python

import heapq
def minMeetingRooms(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

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++

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();                  // 堆大小的峰值 = 最少房间数
}