253. 会议室 II

题目链接（中等）

题目描述

给你一个会议时间安排的数组 intervals，其中 intervals[i] = [start_i, end_i] 表示第 i 个会议的开始和结束时间。请你计算并返回所需会议室的最小数量，使得所有会议都能顺利召开（即同一时间一个会议室只能容纳一个会议）。

数据范围：

• 1 <= intervals.length <= 10^4
• 0 <= start_i < end_i <= 10^6

示例

示例 1：

输入： intervals = [[0,30],[5,10],[15,20]]
输出： 2
解释： - 会议 [0,30] 占用会议室 1； - 会议 [5,10] 与 [0,30] 重叠，需要会议室 2； - 会议 [15,20] 开始时 [5,10] 已结束，可复用会议室 2。

因此最少需要 2 间。

示例 2：

输入： intervals = [[7,10],[2,4]]
输出： 1
解释： 两个会议时间不重叠，可以共用一间会议室。

核心思路

本题本质：求最多有多少个会议同时进行。因为同一时刻正在进行的会议数，就是所需的最少会议室数量。

两种经典解法：

1. 排序 + 最小堆：按开始时间排序，用最小堆维护「正在进行的会议的结束时间」，堆顶是最早结束的会议；
2. 扫描线：把每个会议拆成「开始」和「结束」两个事件，按时间排序后扫描，同时进行的最大数量就是答案。

---

方法一：排序 + 最小堆

思路及解法

直觉：给每个会议分配会议室时，总是优先复用最早结束的会议室。用一个最小堆维护「正在使用的会议室的结束时间」，堆顶就是最早结束的那个。

流程：

1. 按开始时间升序排序所有会议；
2. 用最小堆 heap 存储「当前正在进行的会议的结束时间」；
3. 遍历每个会议 [start, end]：
   • 若 heap 非空且 start >= heap[0]（最早结束的会议已经结束），说明有空闲会议室，弹出堆顶，把当前会议的 end 压入堆（复用该会议室）；
   • 否则，说明所有会议室都在使用中，需要新开一间，直接把 end 压入堆；
4. 遍历结束后，堆的大小就是所需最少会议室数量。

为什么这样是对的？

• 会议室总数 = 某个时刻正在进行的会议数的最大值；
• 堆中每个元素代表一间「正在被占用」的会议室；
• 只有当某个会议结束时，才腾出会议室给新会议复用；
• 堆的大小在遍历过程中不断变化，最大值就是所需数量。

代码

class Solution:
    def minMeetingRooms(self, intervals: list[list[int]]) -> int:
        if not intervals:
            return 0
        intervals.sort(key=lambda x: x[0])
        heap = [intervals[0][1]]

        for i in range(1, len(intervals)):
            start, end = intervals[i]
            if start >= heap[0]:
                heapq.heapreplace(heap, end)
            else:
                heapq.heappush(heap, end)

        return len(heap)

复杂度分析

• 时间复杂度：$O(n \log n)$，排序 $O(n \log n)$，每个会议入堆/出堆 $O(\log n)$。
• 空间复杂度：$O(n)$，最坏情况下所有会议同时进行，堆的大小为 $n$。

---

方法二：扫描线（上下车算法）

思路及解法

把会议看成「上车」和「下车」两个事件：

• 开始时间 start 是上车（占用 +1）；
• 结束时间 end 是下车（占用 -1）。

把每个会议拆成两个事件，按时间排序，然后从左到右扫描：

• 遇到 +1：同时进行的会议数 +1；
• 遇到 -1：同时进行的会议数 -1；
• 过程中同时进行的会议数的最大值就是所需最少会议室数。

关键细节：时间相同时，结束事件（-1）要排在开始事件（+1）前面。

因为一个会议在时刻 t 结束，另一个会议可以在时刻 t 立即开始，不需要额外会议室。

举例：intervals = [[0,30],[5,10],[15,20]]

事件列表（已排序）：

时间	事件	delta
0	开始	+1
5	开始	+1
10	结束	-1
15	开始	+1
20	结束	-1
30	结束	-1

扫描过程：

时间	delta	当前数	最大值
0	+1	1	1
5	+1	2	2
10	-1	1	2
15	+1	2	2
20	-1	1	2
30	-1	0	2

最大值是 2，即答案。

代码

class Solution:
    def minMeetingRooms(self, intervals: list[list[int]]) -> int:
        events = []
        for start, end in intervals:
            events.append((start, 1))
            events.append((end, -1))

        events.sort(key=lambda x: (x[0], x[1]))

        max_rooms = 0
        current_rooms = 0
        for _, delta in events:
            current_rooms += delta
            max_rooms = max(max_rooms, current_rooms)

        return max_rooms

复杂度分析

• 时间复杂度：$O(n \log n)$，主要是排序 $2n$ 个事件。
• 空间复杂度：$O(n)$，存储 $2n$ 个事件。

---

两种方法对比

方法	时间	空间	特点
排序 + 最小堆	$O(n \log n)$	$O(n)$	符合「贪心复用最早结束」的直觉
扫描线	$O(n \log n)$	$O(n)$	把问题转成「最多同时有几个区间重叠」

推荐：

• 面试：首选最小堆，因为「贪心复用最早结束的会议室」这个思路更贴近实际场景，也更容易讲清楚；
• 想代码短：用扫描线，代码很短，但要注意「结束事件排在开始事件前」这个细节。

---

关键细节

1. 为什么「同时进行的最大会议数」就是答案

在任一时刻，同时进行的会议必须各占一间会议室，所以所需会议室数 ≥ 同时进行的会议数的最大值。

反过来，我们总能用一个贪心策略（每次复用最早结束的会议室）做到「会议室数 = 同时进行的最大值」。因此两者相等。

2. 最小堆中为什么要存「结束时间」

• 判断能否复用会议室，只需知道「最早结束的会议何时结束」；
• 最小堆的堆顶就是这个最早结束时间；
• 用 start >= heap[0] 判断即可。

3. heapreplace 和 heappush 的区别

heapq.heapreplace(heap, end)   # 弹出堆顶并压入 end，一步完成，O(log n)
heapq.heappush(heap, end)      # 只压入 end，不弹出，O(log n)

复用会议室时用 heapreplace（替换掉已结束的那个），新开会议室时用 heappush。

4. 扫描线中「结束事件排前面」的原因

• 如果一个会议在时刻 t 结束，另一个会议在时刻 t 开始，它们不重叠，可以复用会议室；
• 所以 -1 要排在 +1 前面，保证同一时刻先「下车」再「上车」，不会多算一间。

5. 与方法一「合并区间」（LC 56）的区别

• LC 56 合并区间：合并所有重叠的区间，关注区间的合并结果；
• LC 253 会议室 II：关注同时重叠的区间最多有几个，即最大重叠数。

两题思路不同，不要混淆。

---

总结

• 本质：求区间集合的最大重叠数，即同时进行的最多会议数；
• 方法一（最小堆）：
  • 按开始时间排序；
  • 最小堆维护正在进行的会议的结束时间；
  • 复用条件：start >= heap[0]，用 heapreplace 替换；
  • 否则 heappush 新开；
  • 答案 = 堆大小；
• 方法二（扫描线）：
  • 把每个会议拆成 (start, +1) 和 (end, -1)；
  • 时间相同时 -1 排在 +1 前面；
  • 扫描时维护当前重叠数，取最大值；
• 时间复杂度：两种方法都是 $O(n \log n)$，主要开销在排序。

相关题目

• LC 252. 会议室（判断一个人是否能参加所有会议）
• LC 56. 合并区间（合并所有重叠区间）
• LC 435. 无重叠区间（移除最少区间使剩余不重叠）
• LC 1094. 拼车（扫描线的典型应用）