面试官最爱问的合并区间，我用Java Lambda和排序5分钟讲清楚（附牛客Top200原题）

在技术面试中，算法题往往是考察候选人逻辑思维和编码能力的重要环节。合并区间作为一道经典的高频面试题，不仅考验对基础数据结构的掌握，更检验开发者能否将复杂问题拆解为可执行的步骤。今天我们就来聊聊如何用Java的Lambda表达式和排序算法，在5分钟内清晰地向面试官阐述这道题的解题思路。

1. 理解合并区间的核心逻辑

合并区间的本质是将重叠或相邻的区间合并为一个更大的区间。想象你手上有多个时间段安排，有些时间段相互重叠，这时候就需要将它们合并成连续的时间块。这个过程需要解决两个关键问题：

1. 如何判断两个区间是否重叠：对于区间[a,b]和[c,d]，如果c ≤ b，说明两个区间有重叠部分。
2. 如何合并重叠区间：合并后的新区间左边界取两者最小值，右边界取两者最大值。

提示：面试时可以用白板画图辅助说明，比如画出几个重叠的线段，直观展示合并过程。

2. 解题步骤拆解

2.1 排序预处理

合并区间的第一步是对所有区间按照起始点进行排序。这是解题的关键前置步骤，因为：

• 排序后，重叠的区间会相邻排列，大大简化合并逻辑
• 只需要一次线性扫描就能完成所有合并操作

在Java中，我们可以用Lambda表达式简洁地实现排序：

Collections.sort(intervals, (a, b) -> a.start - b.start);

这段代码做了三件事：

1. 使用Collections.sort进行排序
2. 通过Lambda表达式定义比较规则
3. 比较两个区间的start值决定顺序

2.2 合并算法实现

排序后的合并过程可以描述为：

1. 初始化结果集和当前合并区间
2. 遍历每个区间：
   • 如果与当前区间重叠，合并它们
   • 如果不重叠，将当前区间加入结果，开始新的合并
3. 处理最后一个区间

对应的Java代码结构：

List<Interval> result = new ArrayList<>();
Interval current = intervals.get(0);

for (int i = 1; i < intervals.size(); i++) {
    Interval next = intervals.get(i);
    if (current.end >= next.start) { // 重叠
        current.end = Math.max(current.end, next.end);
    } else { // 不重叠
        result.add(current);
        current = next;
    }
}
result.add(current); // 添加最后一个区间

3. 面试中的常见追问与应对

3.1 时间复杂度分析

面试官通常会问："这个算法的时间复杂度是多少？"

可以这样回答：

• 排序阶段：O(n log n)，因为使用了快速排序
• 合并阶段：O(n)，只需一次线性扫描
• 总体复杂度：O(n log n)，由排序步骤决定

3.2 边界条件处理

有经验的面试官会考察你对边界情况的考虑：

1. 空输入处理：如果输入列表为空，直接返回空列表
2. 单区间处理：只有一个区间时无需合并
3. 完全包含情况：一个区间完全包含在另一个区间内

代码中的防御性编程：

if (intervals == null || intervals.size() == 0) {
    return new ArrayList<>();
}

3.3 Lambda表达式原理

如果面试官深入询问Lambda表达式：

"Java 8的Lambda本质上是函数式接口的简洁实现。这里的比较器可以用Lambda替代匿名类，使代码更清晰。编译器会根据上下文推断参数类型和返回值。"

4. 牛客Top200原题实战

让我们看一道来自牛客网Top200的真实题目：

题目描述： 给出一个区间的集合，请合并所有重叠的区间。

示例： 输入：[[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]]

完整解决方案：

public List<Interval> merge(List<Interval> intervals) {
    if (intervals == null || intervals.isEmpty()) {
        return new ArrayList<>();
    }
    
    // 按起始点排序
    intervals.sort((a, b) -> Integer.compare(a.start, b.start));
    
    List<Interval> merged = new ArrayList<>();
    Interval current = intervals.get(0);
    
    for (int i = 1; i < intervals.size(); i++) {
        Interval next = intervals.get(i);
        if (current.end >= next.start) {
            current.end = Math.max(current.end, next.end);
        } else {
            merged.add(current);
            current = next;
        }
    }
    merged.add(current);
    
    return merged;
}

5. 面试表达技巧

5.1 分步骤讲解

向面试官讲解时，建议采用"总-分-总"结构：

1. 先概述问题本质（区间合并）
2. 拆解关键步骤（排序→合并）
3. 最后总结优化点

5.2 可视化辅助

可以在白板上画出这样的示例：

区间图示例：
[1-----3]
   [2-------6]
            [8----10]
                     [15----18]

5.3 代码书写规范

面试中写代码时注意：

• 方法签名清晰
• 变量命名有意义
• 适当添加注释
• 先处理边界条件

6. 变种问题准备

有经验的面试官可能会延伸提问：

1. 插入新区间：如何在已合并的区间列表中插入一个新区间并保持合并状态？
2. 求交集：如何求两个已排序区间列表的交集？
3. 会议室安排：给定一组会议时间，问最少需要多少会议室？

对于这类问题，核心思路仍然是排序+线性扫描，只是判断条件和合并逻辑稍有不同。