跳至主要內容

LeetCode 253. 会议室II——差分数组与扫描线两种解法

老张2026/4/30大约 7 分钟

LeetCode 253. 会议室II——差分数组与扫描线两种解法

适读人群：Java 中级工程师、备战面试的同学 | 阅读时长：约22分钟 | 难度：中等

开篇故事

会议室II 是面试里出现频率极高的「资源调度」类题，也是理解扫描线算法的绝佳入口。

题目看起来是个调度问题，但本质上是一个「最大重叠区间数」问题：在所有会议中，同时进行的会议最多有几个？这个最大值就是所需的最少会议室数。

这道题我见过三种解法：差分数组（从上一篇自然延伸）、扫描线 + 排序（更通用的模板）、以及贪心 + 优先队列（面试最常见的期望解法）。三种解法各有侧重，理解了这道题，就算真正入门了「区间调度」这类问题。

一、题目解析

题目描述：

给你一个会议时间安排的数组 intervals，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi]，返回所需会议室的最小数量。

示例：

输入：intervals = [[0,30],[5,10],[15,20]]
输出：2

输入：intervals = [[7,10],[2,4]]
输出：1

核心理解： 需要的会议室数 = 某一时刻同时进行的会议数的最大值。

二、解法一：差分数组

思路分析

和拼车一样，用差分数组记录每个时间点的「会议开始/结束」变化，最后求前缀和的最大值。

import java.util.*;

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if (intervals == null || intervals.length == 0) return 0;
        
        // 找时间范围
        int maxTime = 0;
        for (int[] interval : intervals) {
            maxTime = Math.max(maxTime, interval[1]);
        }
        
        // 差分数组
        int[] diff = new int[maxTime + 1];
        for (int[] interval : intervals) {
            diff[interval[0]]++;  // 开始时间：+1
            diff[interval[1]]--;  // 结束时间：-1（会议在end时刻结束）
        }
        
        // 求前缀和，取最大值
        int current = 0, maxRooms = 0;
        for (int i = 0; i <= maxTime; i++) {
            current += diff[i];
            maxRooms = Math.max(maxRooms, current);
        }
        
        return maxRooms;
    }
}

复杂度分析

  • 时间复杂度：O(n + maxTime)。
  • 空间复杂度：O(maxTime)。

当 maxTime 很大（比如 10^9），这个方法空间会爆，需要改用离散化。

三、解法二：扫描线 + 排序

核心思想

把每个会议的开始和结束拆成独立的「事件」，按时间排序，扫描时维护「当前进行中的会议数」。

同一时刻有结束也有开始时，先处理结束（因为结束的会议室可以被新会议复用）：

import java.util.*;

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        // 将所有时间点展开为事件
        int n = intervals.length;
        int[] starts = new int[n];
        int[] 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, endIdx = 0;
        for (int i = 0; i < n; i++) {
            if (starts[i] < ends[endIdx]) {
                // 新会议在最早结束的会议结束前开始，需要额外会议室
                rooms++;
            } else {
                // 新会议可以复用最早结束的那个会议室
                endIdx++;
            }
        }
        
        return rooms;
    }
}

为什么分开排序有效： 我们只关心某一时刻「进行中会议数」的最大值，不需要知道哪个会议和哪个会议室配对。开始时间排序后从小到大处理，结束时间排序后维护「最早能释放的会议室」。

复杂度分析

  • 时间复杂度：O(n log n)。排序。
  • 空间复杂度：O(n)。

四、解法三（最优）：贪心 + 最小堆

核心思想

按开始时间排序会议。用最小堆维护所有进行中会议的结束时间（堆顶是最早结束的）。

对于每个新会议：

  • 如果最早结束的会议（堆顶）在新会议开始前结束，就让新会议用那个会议室（弹出堆顶，入堆新结束时间）
  • 否则，需要一个新会议室（直接入堆新结束时间）

堆的大小就是当前所需的最小会议室数。

完整代码

import java.util.*;

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if (intervals == null || intervals.length == 0) return 0;
        
        // 按会议开始时间排序
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        
        // 最小堆：维护所有进行中会议的结束时间
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        
        for (int[] interval : intervals) {
            int start = interval[0], end = interval[1];
            
            if (!minHeap.isEmpty() && minHeap.peek() <= start) {
                // 最早结束的会议已经在 start 之前结束，释放该会议室
                minHeap.poll();
            }
            
            // 将当前会议的结束时间加入堆（无论是占用新会议室还是复用）
            minHeap.offer(end);
        }
        
        // 堆的大小 = 所需的最少会议室数
        return minHeap.size();
    }
}

手动模拟

以 intervals = [[0,30],[5,10],[15,20]] 排序后仍相同：

处理startend堆顶操作堆状态
[0,30]030空直接入堆[30]
[5,10]5103030>5，新会议室[10,30]
[15,20]15201010<=15，弹10，入20[20,30]

最终堆大小：2，返回 2。正确！

复杂度分析

  • 时间复杂度：O(n log n)。排序 O(n log n)，堆操作 n 次 O(n log n)。
  • 空间复杂度：O(n)。堆大小。

五、举一反三

区间调度问题家族：

题目贪心策略
252. 会议室I检查区间是否有重叠（按开始排序）
253. 会议室II最少房间数（本题）
435. 无重叠区间最少移除区间数（按结束时间贪心）
56. 合并区间合并重叠区间

六、踩坑实录

坑一：同一时刻开始和结束的处理顺序

如果一个会议在时刻 t 结束，另一个在时刻 t 开始，是否需要两个会议室？

题目给的是 [start, end) 半开区间（通常是「end 时刻释放」），所以 minHeap.peek() <= start（用 <=）表示「最早结束的会议在 start 时刻或之前结束」，可以复用。

如果题目语义不同（end 时刻这个会议室还在使用），应改为 < start。仔细读题，这个细节很重要。

坑二：差分数组在时间范围大时会 MLE

如果 intervals[i][1] 可以到 10^9，开 10^9+1 大小的差分数组直接 MLE。这时需要离散化：把所有时间点压缩到 [0, 2n-1] 范围内。

// 离散化思路
Set<Integer> timeSet = new TreeSet<>();
for (int[] interval : intervals) {
    timeSet.add(interval[0]);
    timeSet.add(interval[1]);
}
// 建立 时间 -> 压缩后下标 的映射
Map<Integer, Integer> compress = new HashMap<>();
int idx = 0;
for (int t : timeSet) compress.put(t, idx++);

会议室II 题目里时间范围没有明确限制，用最小堆的解法就不存在这个问题。

坑三：返回的是堆大小，不是堆的最大历史大小

最小堆的大小随着会议释放和加入而变化。最终堆大小不一定是最大值！

但仔细看：我们每处理一个会议时，要么弹出一个（会议室复用），要么直接加入（新会议室）。整个过程中堆的大小就是「当前需要的会议室数」，而且处理到某个时间点时，堆大小就是「这个时间点正在进行的会议数」。

最终堆大小 = 处理完所有会议后所需的会议室总数 = 答案。

这个推导是正确的，因为每次弹出旧的再入新的，会议室总数不变；每次没有弹出直接入，会议室总数+1。

七、总结

会议室II 用三种方法展示了「区间重叠计数」的不同角度：

  • 差分数组：以时间轴为视角，统计每个时刻的会议数，取最大值
  • 扫描线排序：分离开始/结束时间，双指针扫描，O(n log n)
  • 贪心堆：模拟会议室分配过程，用最小堆维护最早释放的会议室

三种方法的核心都是：同一时刻进行的会议数越多，需要的会议室越多，答案是这个数的最大值。

编辑此页
最近更新:
贡献者: xiaozhangge