会议室 II：最少需要多少间会议室？（LeetCode 253）

简化版

给一组会议时间 [start, end]，求最少需要多少间会议室才能安排下全部会议（同一时刻并行的会议要各占一间）。本质是求「任意时刻同时进行的会议数的最大值」。两种主流解法：① 最小堆——按开始时间排会议，堆里存正在进行的会议的结束时间，新会议开始时若堆顶（最早结束的）已结束就复用该房间，否则新开一间，堆的最大大小即答案；② 扫描线/差分——把开始 +1、结束 −1 排序后扫描，计数峰值即答案。

详细版

解法一：最小堆（O(n log n)）

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[] meet : intervals) {
        if (!heap.isEmpty() && heap.peek() <= meet[0]) {
            heap.poll();          // 最早结束的会议已散，腾出这间房
        }
        heap.offer(meet[1]);      // 当前会议占用一间房（复用或新开）
    }
    return heap.size();           // 堆的大小 = 峰值并行数 = 房间数
}

解法二：扫描线 / 差分（O(n log n)）

int minMeetingRooms(int[][] intervals) {
    int n = intervals.length;
    int[] starts = new int[n], ends = new int[n];
    for (int i = 0; i < n; i++) { starts[i] = intervals[i][0]; ends[i] = intervals[i][1]; }
    Arrays.sort(starts); Arrays.sort(ends);
    int rooms = 0, maxRooms = 0, j = 0;
    for (int i = 0; i < n; i++) {
        while (j < n && ends[j] <= starts[i]) { rooms--; j++; }  // 已结束的先释放
        rooms++;                                                 // 当前会议开始
        maxRooms = Math.max(maxRooms, rooms);
    }
    return maxRooms;
}

答案 = 最大同时并行会议数（重叠峰值），不是简单的区间数。
堆法：堆里始终是「当前正在进行的会议」，大小的峰值即所需房间。
扫描线法：开始事件 +1、结束事件 −1，计数峰值即答案。
复杂度：两法都是 O(n log n)（排序主导）。

完整版教学

一、题意转化：房间数 = 时间轴上的最大重叠数

关键要想通：需要的会议室数量，等于「某一瞬间同时进行的会议数」的最大值。想象把所有会议画在时间轴上，某个时刻竖着切一刀，切到几个区间，那一刻就需要几间房；整条轴上切到的最多区间数，就是必须准备的房间数。所以本题 = 求区间的最大重叠层数。这和会议室 I（只判断是否有重叠）完全不同层级。

二、解法一：最小堆维护「正在进行的会议」

按开始时间排序后依次处理每个会议。用一个最小堆存放当前所有「正在进行」的会议的结束时间（堆顶是最早结束的那个）：

处理新会议时，看堆顶——最早结束的会议是否已经在新会议开始前结束（堆顶 <= 新会议.start）。若是，说明那间房空出来了，poll() 复用它。
无论是否复用，都把新会议的结束时间 offer 进堆（它现在占一间房）。
遍历完，堆在过程中达到的最大 size 就是峰值并行数。代码里因为每次最多释放一间、必占一间，最终 heap.size() 恰好等于整个过程的峰值（房间只增不减地累积到峰值）。

直觉：堆就是「当前开着的会议 = 正在用的房间」，堆多大就用了多少房。

三、解法二：扫描线 / 差分

把每个会议拆成两个事件：start 时刻「+1」（要一间房），end 时刻「−1」（腾一间房）。把所有事件按时间排序后从左扫到右，维护当前房间计数，峰值即答案。

实现上常用「开始数组、结束数组分别排序，双指针扫」：遍历排好序的开始时间，每遇到一个开始就 rooms++；同时用指针 j 追赶已排序的结束时间，凡是 ends[j] <= starts[i] 的会议都已散会，rooms--。过程中记录 rooms 的最大值。

边界：ends[j] <= starts[i] 用 <=，表示「上一个会议在新会议开始的同一刻结束，房间可无缝复用」（相接不占两间）。若题目认为相接也要两间，改成 <。

四、两种解法的对比

	最小堆	扫描线/差分
思路	维护正在进行的会议集合	开始 +1、结束 −1 求峰值
直观性	贴近「房间复用」的现实	贴近「时间轴重叠计数」
复杂度	O(n log n)	O(n log n)
扩展	易扩展到「输出每间房的安排」	易扩展到「天际线、区间覆盖计数」

两种都要掌握：堆法更好讲「房间复用」的故事，扫描线法是「区间重叠计数」的通用武器（天际线问题 218 也是它）。

五、易错点

误以为答案是区间总数或不重叠组数。答案是最大重叠层数，别和无重叠区间 435（最多不重叠数）搞混。
堆里存错东西：要存「结束时间」并用最小堆，堆顶是最早结束的。存开始时间是错的。
相接边界：会议 [9,10] 和 [10,11] 通常不需要两间房（10 点无缝交接），判断用 <= 释放房间。按题意确认。

六、排序键、扫描不变量与边界语义

本题扫描成立的结构是：答案是任一时刻同时进行会议数的最大值；堆保存已分配房间的最早结束时间。

新会议开始前弹出所有已结束会议可复用房间；或双数组扫描 start/end 事件

数字推演：[0,30],[5,10],[15,20] 在时刻5重叠2场，最少2间。

扫描过程中要始终说明已经处理部分被压缩成什么状态，以及为什么更早区间不必再看。实现边界是：端点相等时先处理结束再开始；堆法可只弹一个也能算房间数，但弹尽更准确表达活跃集合。

记忆钩子：区间题先写端点语义，再选排序键；小于还是小于等于不是代码风格，而是问题定义。

七、方法对比与专项测试

问题结构	常用工具
静态合并或覆盖	排序后线性扫描
选择最多不重叠	按右端排序的贪心
最大同时重叠	扫描线或最小堆
两个有序列表求交	双指针
动态预约	有序树或线段树

测试必须覆盖空输入、单区间、完全分离、完全嵌套、链式重叠、相同起点或终点，以及端点恰好相接。若排序比较器用端点相减，还要加入整数极值检查溢出。

正确性复核要落到本题的排除逻辑：答案是任一时刻同时进行会议数的最大值；堆保存已分配房间的最早结束时间。这保证扫描指针越过某段后，它不可能再与未来候选形成更优或遗漏的答案。

已处理区间 ──压缩为边界/堆/结果尾段──> 当前区间
       │                                  │
       └─ 已由排序与端点关系证明无需回看 ─┘
当前决策完成后，指针只向右移动

在数字样例“[0,30],[5,10],[15,20] 在时刻5重叠2场，最少2间”上，应逐轮写出被保留的边界和被丢弃的区间。若某一步无法解释为什么丢弃安全，就说明排序键、端点不等号或状态定义仍有问题。

工程上还要单独确认：端点相等时先处理结束再开始；堆法可只弹一个也能算房间数，但弹尽更准确表达活跃集合。这些条件变化会直接改变重叠判定或所需数据结构，不能只修改一个比较符后沿用原证明。

八、常见误区与追问

误区：堆大小最终值就是答案。 若不维护最大值且会弹出，最终大小未必是峰值。
误区：端点相等需要新房间。 半开会议可复用刚结束房间。
误区：只看相邻会议能算房间数。 并发数可能由多个跨越区间共同形成。
追问：堆里存什么？ 当前占用房间的结束时间。
追问：扫描线为何可行？ 房间需求等于活跃区间计数最大值。
追问：两解法复杂度？ 均 O(n log n)，双数组扫描排序后 O(n)。

九、加强记忆

会议室 II（最少房间数）= 求区间的最大重叠层数（某瞬间最多几个会议并行）。堆法：按开始时间排序，最小堆存「正在进行会议的结束时间」，新会议开始时若堆顶已结束就复用、否则新开，堆的峰值 size = 房间数。扫描线法：开始 +1、结束 −1，排序后扫描取计数峰值（或开始/结束数组各自排序、双指针）。相接可复用房间用 <=。别和「最多不重叠数」混。O(n log n)。

简化版

详细版