LeetCode 56. 合并区间——排序+贪心合并的边界处理

适读人群：Java初中级工程师、需要掌握区间处理技巧的同学 | 阅读时长：约20分钟 | 难度：中等

---

开篇故事

在做日历系统开发的时候，我曾经遇到过一个真实的业务需求：用户在日历上创建了多个事件，有些事件时间段有重叠，产品要求把重叠的事件合并显示成一个长时间块。这不就是 LeetCode 56 的现实版本吗？

当时我的第一版实现思路非常粗暴——对每个区间，和已有的所有区间逐一比较，有重叠就合并，直到没有区间可以继续合并为止。这个算法在日历事件少的时候还好，一旦用户创建了几百个事件，界面卡成了幻灯片。

后来优化成先排序再线性扫描的方案，性能提升了几十倍。这次的优化经历让我深刻理解了排序在区间问题中的核心价值：排序把一个"二维问题"（任意两个区间可能重叠）变成了"一维问题"（只需要看相邻区间是否重叠）。今天就把这个经典题彻底讲清楚。

---

一、题目解析

题目： 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi]。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例：

• 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]，输出：[[1,6],[8,10],[15,18]] （[1,3]和[2,6]重叠，合并为[1,6]）
• 输入：intervals = [[1,4],[4,5]]，输出：[[1,5]] （[1,4]和[4,5]共享端点，视为重叠需要合并）

关键约束：

• 1 <= intervals.length <= 10^4
• 端点相等算重叠（与上题不同！）

本质分析： 合并区间有三种情况需要处理：

1. 完全不重叠：[1,2]和[3,4]，保持各自独立。
2. 部分重叠：[1,3]和[2,4]，合并为[1,4]。
3. 完全包含：[1,5]和[2,3]，合并为[1,5]（被包含的消失）。

端点相等也算重叠：[1,3]和[3,5]，合并为[1,5]。

排序后的关键洞察：按开始时间排序后，区间 i 和区间 i+1 如果重叠，其合并结果的右边界是两者右边界的最大值（处理"完全包含"情况）；如果不重叠，直接将区间 i 加入结果集，然后从区间 i+1 重新开始。

---

二、解法一：暴力合并（双重循环迭代）

思路

反复扫描区间列表，每次找到两个重叠的区间就合并，直到没有重叠为止。

代码

import java.util.*;

public class Solution_Brute {
    public int[][] merge(int[][] intervals) {
        List<int[]> list = new ArrayList<>(Arrays.asList(intervals));
        boolean merged = true;
        
        while (merged) {
            merged = false;
            for (int i = 0; i < list.size() && !merged; i++) {
                for (int j = i + 1; j < list.size() && !merged; j++) {
                    int[] a = list.get(i);
                    int[] b = list.get(j);
                    // 判断是否重叠：a的开始 <= b的结束 且 b的开始 <= a的结束
                    if (a[0] <= b[1] && b[0] <= a[1]) {
                        // 合并
                        int[] newInterval = {
                            Math.min(a[0], b[0]),
                            Math.max(a[1], b[1])
                        };
                        list.remove(j);
                        list.remove(i);
                        list.add(newInterval);
                        merged = true;
                    }
                }
            }
        }
        
        return list.toArray(new int[0][]);
    }
}

复杂度分析

• 时间复杂度： O(n³)，最坏情况下每轮只合并一对，共 n/2 轮，每轮双重循环 O(n²)。
• 空间复杂度： O(n)，结果列表。
• 缺点： 效率极差，完全不可用于大数据。写出来仅为说明暴力思路。

---

三、解法二：排序+栈

思路

按开始时间排序后，用栈维护合并后的区间集合。遍历每个区间，与栈顶区间比较：

• 重叠：弹出栈顶，将合并后的区间入栈。
• 不重叠：直接入栈。

代码

import java.util.*;

public class Solution_Stack {
    public int[][] merge(int[][] intervals) {
        // 按开始时间排序
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        
        Deque<int[]> stack = new ArrayDeque<>();
        
        for (int[] interval : intervals) {
            if (stack.isEmpty() || stack.peek()[1] < interval[0]) {
                // 栈为空或栈顶区间与当前区间不重叠（注意：端点相等时重叠，所以条件是 <）
                stack.push(interval);
            } else {
                // 重叠，合并：更新栈顶的右边界为两者最大值
                int[] top = stack.pop();
                stack.push(new int[]{top[0], Math.max(top[1], interval[1])});
            }
        }
        
        // 将栈中内容转为数组（注意栈是反序的，需要转置）
        int[][] result = new int[stack.size()][2];
        int idx = stack.size() - 1;
        while (!stack.isEmpty()) {
            result[idx--] = stack.pop();
        }
        
        return result;
    }
}

复杂度分析

• 时间复杂度： O(n log n)，排序主导，扫描是 O(n)。
• 空间复杂度： O(n)，栈空间（最坏情况所有区间都不重叠）。

---

四、解法三：排序+线性扫描（最优解）

思路

不用栈，直接用 List 存储结果，每次与结果集最后一个区间比较。这样代码更简洁，逻辑更清晰。

关键边界： 判断两个排序后相邻区间 prev 和 curr 是否重叠的条件是 curr[0] <= prev[1]（注意等号，端点相等也要合并）。合并时右边界取两者最大值（处理"curr 被 prev 完全包含"的情况）。

代码

import java.util.*;

public class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length <= 1) return intervals;
        
        // 按开始时间升序排序
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        
        List<int[]> result = new ArrayList<>();
        result.add(intervals[0]); // 将第一个区间加入结果
        
        for (int i = 1; i < intervals.length; i++) {
            int[] curr = intervals[i];
            int[] last = result.get(result.size() - 1); // 结果集中最后一个区间
            
            if (curr[0] <= last[1]) {
                // 重叠（包括端点相等），合并：右边界取最大值
                // 注意：不需要更新左边界，因为按开始时间排序，curr[0] >= last[0]
                last[1] = Math.max(last[1], curr[1]);
            } else {
                // 不重叠，直接加入结果
                result.add(curr);
            }
        }
        
        return result.toArray(new int[result.size()][]);
    }
}

关键细节解释

1. 为什么排序后只需和结果集最后一个区间比较？

   按开始时间排序后，如果 curr 与结果集最后一个区间不重叠（curr[0] > last[1]），由于 curr 的开始时间是当前最大的，所以 curr 与结果集中更早的所有区间也不重叠（它们的结束时间更早，更不可能与 curr 重叠）。

2. 为什么合并时只需更新右边界，不需要更新左边界？

   按开始时间排序，curr[0] >= last[0] 恒成立。合并后的区间开始时间仍是 last[0]，不需要更新。

3. 为什么 last[1] = Math.max(last[1], curr[1]) 而不是 last[1] = curr[1]？

   处理"完全包含"情况：如果 curr 被 last 完全包含（curr[1] <= last[1]），直接赋值会缩小右边界，导致错误。必须取最大值。

复杂度分析

• 时间复杂度： O(n log n)，排序主导，线性扫描 O(n)。
• 空间复杂度： O(n)，结果列表（最坏情况所有区间都不重叠）。

---

五、举一反三

同类题目

LeetCode 57. 插入区间 给一个已经排好序且不重叠的区间列表，插入一个新区间并合并。思路：分三段处理——新区间左侧的所有区间、与新区间重叠的所有区间（逐一合并）、新区间右侧的所有区间。

public int[][] insert(int[][] intervals, int[] newInterval) {
    List<int[]> result = new ArrayList<>();
    int i = 0, n = intervals.length;
    
    // 1. 加入所有在新区间左侧的区间（结束时间 < 新区间开始时间）
    while (i < n && intervals[i][1] < newInterval[0]) {
        result.add(intervals[i++]);
    }
    
    // 2. 合并所有与新区间重叠的区间
    while (i < n && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
        i++;
    }
    result.add(newInterval);
    
    // 3. 加入所有在新区间右侧的区间
    while (i < n) result.add(intervals[i++]);
    
    return result.toArray(new int[0][]);
}

LeetCode 986. 区间列表的交集 给两个区间列表，求所有交集区间。双指针，每次取两个指针指向区间的交集（若存在），然后将结束时间较小的指针向前推进。

区间问题综合模板

// 区间合并通用步骤
// 1. 按开始时间排序（合并类问题）或按结束时间排序（选取类问题）
// 2. 线性扫描，维护当前"活跃区间"
// 3. 根据重叠情况：合并（更新右边界）或另起（加入结果集）

---

六、踩坑实录

坑一：忘记处理"完全包含"的情况

// 错误写法：直接用curr[1]覆盖
last[1] = curr[1]; // 如果last=[1,5],curr=[2,3]，结果变成[1,3]，丢失了[3,5]部分！

// 正确写法：取最大值
last[1] = Math.max(last[1], curr[1]);

这是合并区间最经典的坑，我当年第一次写这道题就踩了。反例：[[1,5],[2,3]]，排序后是[[1,5],[2,3]]，[2,3]被[1,5]完全包含，合并结果应该是[[1,5]]。如果写 last[1] = curr[1]，结果变成[[1,3]]，完全错误。

坑二：result.toArray 的参数

// 常见的两种写法
result.toArray(new int[0][]);    // 推荐：JVM会自动分配合适大小的数组
result.toArray(new int[result.size()][]);  // 也正确，显式指定大小

不能用 (int[][]) result.toArray()，这样会抛 ClassCastException。

坑三：直接修改了 intervals 数组的内容

在解法三中，last[1] = Math.max(last[1], curr[1]) 直接修改了 result 列表中已有区间（last）的值，而 last 是 intervals[i] 的引用（当 i=0 时），所以实际上也修改了原始输入。如果题目要求不修改输入，需要 result.add(new int[]{...}) 而不是直接 result.add(intervals[i])，然后合并时创建新数组。

坑四：对排序稳定性的错误假设

有时会遇到 [1,4] 和 [1,3] 这样开始时间相同的区间，按开始时间排序后两者顺序不确定。但这不影响正确性，因为无论哪个先进入结果，另一个和它的重叠情况处理逻辑完全一样。

坑五：区间长度为0（单点区间）

intervals[i][0] == intervals[i][1] 是合法的，表示一个单点区间。两个单点区间 [x,x] 和 [x,x]，按照"端点相等算重叠"的规则，它们应该合并为 [x,x]。这种情况我们的代码已经正确处理了，但要注意不要在其他地方假设"区间长度 > 0"。

---

七、总结

合并区间这道题的代码不复杂，但细节很多，尤其是边界条件的处理。掌握这道题有三个关键点：

1. 排序是前提：按开始时间排序后，将二维比较问题降为一维比较，只需与结果集最后一个区间比较。
2. 合并时取右边界最大值：必须用 Math.max，不能直接赋值，否则"完全包含"情况会出错。
3. 端点相等的处理：题目说端点相等算重叠，所以不重叠的条件是 curr[0] > last[1]（严格大于），重叠的条件是 curr[0] <= last[1]（含等号）。

解法	时间复杂度	空间复杂度	推荐程度
暴力双重循环	O(n³)	O(n)	仅供理解
排序+栈	O(n log n)	O(n)	可接受
排序+线性扫描	O(n log n)	O(n)	推荐

---

补充深入讲解：合并区间的算法本质与工程实践

为什么排序是核心操作

很多同学在学合并区间时只记住了"排序后扫描"这个步骤，却没有真正理解为什么排序是必要的。让我们从数学角度分析一下。

不排序的情况下，判断区间是否重叠是一个二维问题：任意两个区间可能重叠，需要 O(n²) 的比较次数。而按开始时间排序后，这个问题降为一维问题：只需要检查相邻的两个区间是否重叠。这是因为排序保证了"如果区间 i 和区间 j 不重叠（j > i），则区间 i 和区间 k（k > j）一定也不重叠"——排序消除了远距离区间之间的相关性，使得线性扫描成为可能。

排序操作是从"全局比较"到"局部比较"的降维变换，这在算法设计中是一种非常重要的思想。很多看似需要 O(n²) 的问题，经过适当排序后都能降到 O(n log n) 甚至 O(n)。

合并区间的三种形态详解

理解合并区间，需要对三种重叠形态有清晰的认识：

第一种形态：部分重叠（Partial Overlap）

例如 [1,3] 和 [2,5]，两者有一段共同时间区间 [2,3]。合并后是 [1,5]：左端点取较小值（1），右端点取较大值（5）。这是最直观的合并情况。

第二种形态：完全包含（Complete Containment）

例如 [1,8] 和 [2,5]，第二个区间完全被第一个包含。合并后仍是 [1,8]：左端点取 min(1,2)=1，右端点取 max(8,5)=8。这是很多初学者容易出错的情况——如果不取右端点的最大值，而是直接用 curr[1] 覆盖，结果会缩小到 [1,5]，丢失了 [5,8] 这段范围。

第三种形态：端点相邻（Adjacent Endpoints）

例如 [1,3] 和 [3,5]，它们在点 3 处相接。根据题目定义，这属于需要合并的情况（curr[0] <= last[1]，即 3 <= 3）。合并后是 [1,5]。注意这里用 <= 而不是 <，这正对应了"端点相等算重叠"的约定。

代码中 last[1] = Math.max(last[1], curr[1]) 这一行，同时正确处理了以上三种情况。这是整个算法最精华的一行，不要小看它。

工程中的合并区间

在我做实时数据处理系统时，有个需求：用户的在线时段记录可能有重叠（比如同一个用户在多台设备上的活跃时间），需要合并后计算用户的总在线时长。这就是合并区间的直接应用。

数据规模：每天大约 10^8 条记录，每个用户平均 50 条时段记录。先按用户 ID 分组，再对每个用户的时段做合并区间处理，最后求合并后各区间的时长之和。整个流程跑在 Spark 上，核心的区间合并逻辑就是这道题的标准解法。

合并区间之后，还可以回答很多衍生问题：某用户的最长连续在线时长是哪段？两个用户的同时在线时段有哪些（区间交集问题）？三个及以上用户的同时在线时段（多个区间列表的交集）？这些都是区间算法家族的重要成员。

与区间题的整体关联

做完合并区间，我们来梳理一下区间题家族的关系：

合并区间（LeetCode 56）——按开始时间排序，合并重叠，关注"合并后的最终形态"。

插入区间（LeetCode 57）——给有序不重叠列表插入一个新区间并合并，关注"插入后的维护"。

移除最少区间（LeetCode 435）——按结束时间排序，贪心保留，关注"最大不重叠子集"。

引爆气球（LeetCode 452）——按右端点排序，贪心覆盖，关注"最少覆盖点"。

区间交集（LeetCode 986）——两个有序不重叠区间列表，双指针求交集，关注"两集合的公共部分"。

这五道题形成了一个完整的区间操作体系。每道题都有独特的排序维度和贪心/扫描策略，但底层思想都是"排序消除二维复杂度"和"线性扫描维护状态"。把这五道题一起复习，是掌握区间算法的最有效路径。

代码健壮性思考

在处理区间问题时，有几个工程上的考虑值得关注：

输入验证：题目保证 intervals[i].length == 2 且 starti <= endi，但实际工程中区间可能来自用户输入或外部数据，需要校验。

并发安全：如果 merge 函数在多线程环境下被调用，且直接修改了 result 列表中的已有区间对象（原地修改 last[1]），会有线程安全问题。生产代码中应该创建新的区间对象而不是修改原有对象。

大数据量：如果区间数量在亿级别，Java 堆内存可能不够。需要用流式处理（Streaming）方式，边读入区间边合并，而不是一次性加载所有区间到内存。

精度问题：如果区间端点是浮点数（比如时间的毫秒级精度），比较时要注意浮点数精度问题，通常建议先转换为整数（如统一用毫秒时间戳）再处理。

---

合并区间算法在数据库中的应用

合并区间在关系型数据库中有一个经典的应用场景：会话合并查询。假设有一张用户登录记录表，记录了用户的每次登录时间和登出时间。由于用户可能在多个设备上同时登录，同一用户的多段在线时间可能有重叠。要求计算每个用户的"净在线时长"（去掉重叠后的总在线时长）。

SQL 实现这个需求非常困难（需要复杂的窗口函数），而在应用层用合并区间算法则清晰简洁：先按用户分组，再对每组的时间段按开始时间排序，然后做一遍线性合并，最后求合并后各段时长之和。这个模式在实际的用户行为分析系统中广泛使用。

另一个数据库应用是连续数值范围合并：在告警系统中，多个监控模块可能对同一资源触发告警，每个告警有开始时间和结束时间。合并这些告警时间段，得到实际的故障持续时间，是告警降噪和根因分析的基础操作。

区间合并的流式处理设计

当区间数据量极大（例如每天产生数亿条日志，每条包含一个时间区间），无法将所有区间一次性加载到内存时，需要流式处理（Streaming）方式。

流式合并区间的设计：假设输入按开始时间有序（通常通过数据管道预排序），维护一个"当前合并区间"[curStart, curEnd]，逐条读入新区间 [s, e]：若 s <= curEnd（重叠），则更新 curEnd = max(curEnd, e)；否则输出当前合并区间，开始新的合并区间。这样只需 O(1) 的工作内存，不需要存储所有区间。

这个流式处理模式在 Apache Flink 等实时流处理框架中非常常见，是"滑动窗口"和"会话窗口"等时间窗口操作的基础实现机制。