Merge Intervals 是 LeetCode Hot 100 里面一道非常经典的区间题。
先排序，再线性扫描。
很多区间类问题的核心都不是暴力比较每一对区间，而是先把区间按某种规则排好序，然后利用排序后的结构特征，一次遍历把答案做出来。 “合并区间”几乎就是这类题最经典的一道模板题。
你给出的这份 Java 代码，使用的正是这道题最标准的一种写法：
-
先按区间左端点排序
-
再从左到右扫描
-
如果当前区间和后面的区间有重叠，就不断扩展右端点
-
最后把合并后的区间加入结果集
本文就结合这段代码，系统地讲一下这道题的解法思路。
题目介绍
给定一个区间集合 intervals，其中：
intervals[i] = [starti, endi]
表示第 i 个区间的起点和终点。
现在要求你合并所有重叠的区间，并返回一个不重叠的区间数组。
例如：
[[1,3],[2,6],[8,10],[15,18]]
其中：
-
[1,3]和[2,6]有重叠 -
所以它们可以合并成
[1,6]
最终结果就是：
[[1,6],[8,10],[15,18]]
这道题的关键在于：
如何快速判断哪些区间应该合并在一起。
示例
示例 1
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
因为：
-
[1,3]和[2,6]重叠，合并成[1,6] -
后面的
[8,10]和[15,18]都不重叠
所以最终结果如上。
示例 2
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
这里要注意，虽然一个区间的结尾等于另一个区间的开头：
4 == 4
它们也算重叠，因此可以合并成：
[1,5]
最直接的想法为什么不好？
如果不先排序，一个很自然的想法可能是：
-
依次取出每个区间
-
去和其他区间比较，看是否重叠
-
如果重叠就合并
-
然后继续重复这一过程
但这种方法会很麻烦：
-
区间两两比较，逻辑复杂
-
很容易重复处理
-
时间复杂度也会偏高
因为你会发现，区间之间的“重叠关系”如果不先整理顺序，会很混乱。
所以这类题最重要的一步通常是：
先排序。
一旦把区间按左端点从小到大排好，整个问题就会变得非常清晰。
核心思路：排序 + 扫描
这道题最经典的思路可以概括成两步：
第一步：按左端点排序
把所有区间按起点从小到大排序。
为什么这样做？
因为排序之后，如果某个区间会和后面的区间重叠，那它只可能和“后面连续的一段区间”发生关系。 而不会出现那种“隔着很远又突然重叠”的混乱情况。
第二步：线性扫描并合并
扫描排序后的区间时，我们维护当前正在合并的区间 [lef, rig]：
-
如果下一个区间的左端点
<= rig，说明发生重叠，可以继续合并 -
合并方式就是更新右端点：
rig = max(rig, 下一个区间右端点)
-
如果下一个区间的左端点
> rig，说明当前区间已经不能再扩展了，就把它加入答案，然后开始处理新的区间
这就是你这段代码的核心逻辑。
Java 代码
下面是你给出的代码，我这里保留原始逻辑，并加上注释：
class Solution {
public int[][] merge(int[][] intervals) {
// 特殊情况：空数组直接返回
if (intervals.length == 0) return new int[0][0];
// 按区间左端点排序
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
List<int[]> ans = new ArrayList<>();
for (int i = 0; i < intervals.length; i++) {
int lef = intervals[i][0], rig = intervals[i][1];
// 只要后一个区间和当前区间有重叠，就不断合并
while ((i + 1 < intervals.length) && intervals[i + 1][0] <= rig) {
rig = Math.max(rig, intervals[i + 1][1]);
i++;
}
// 当前区间已经合并完成，加入答案
ans.add(new int[]{lef, rig});
}
return ans.toArray(new int[ans.size()][0]);
}
}
代码拆解
这段代码虽然不长，但它把区间题最经典的套路体现得非常完整。 下面一步一步来看。
1. 为什么空数组直接返回？
if (intervals.length == 0) return new int[0][0];
因为如果没有任何区间，那显然就没有什么可合并的，直接返回空二维数组即可。
这是一个基础边界情况，但不能漏掉。
2. 为什么一定要先排序？
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
排序是整道题的关键前提。
这里按照每个区间的左端点 start 从小到大排序。
例如：
[[8,10],[1,3],[2,6],[15,18]]
排序后会变成：
[[1,3],[2,6],[8,10],[15,18]]
这样做之后，区间就按“从左到右”的顺序排列好了。 于是当我们扫描某个区间时，只需要考虑它和后面的区间是否连续重叠即可。
如果不排序，你根本没法用一次线性扫描把重叠关系处理干净。
所以这道题的第一反应应该就是：
区间题先排序。
3. 为什么要用 lef 和 rig 记录当前区间？
int lef = intervals[i][0], rig = intervals[i][1];
这里的 lef 和 rig 表示：
当前正在尝试合并的区间的左右边界。
也就是说，从当前位置开始，我们先假设当前区间就是：
[lef, rig]
然后往后看，如果后面的区间和它有重叠，就把它们不断合并进来，直到不能再扩展为止。
所以 lef 和 rig 本质上就是当前“合并中的区间”。
4. 为什么两个区间重叠的判断条件是 intervals[i+1][0] <= rig？
while ((i + 1 < intervals.length) && intervals[i + 1][0] <= rig)
这是判断两个区间是否重叠的关键条件。
假设当前合并区间是：
[lef, rig]
下一个区间是：
[a, b]
只要：
a <= rig
就说明下一个区间的起点没有跑到当前区间右边去，它们仍然有交集或者接触。
例如：
-
[1,3]和[2,6]：2 <= 3，重叠 -
[1,4]和[4,5]：4 <= 4，也算重叠 -
[1,3]和[4,5]：4 > 3，不重叠
所以这个条件完全正确。
5. 为什么合并时只需要更新右端点？
rig = Math.max(rig, intervals[i + 1][1]);
因为区间已经按左端点排序了。
这意味着当前区间的左端点 lef 一定已经是这一组重叠区间里最小的左端点，所以不需要再改。
而右端点则可能被后面的区间继续向右扩展，所以只需要更新：
rig = max(当前右端点, 下一个区间右端点)
例如：
当前区间：
[1,3]
下一个区间：
[2,6]
合并后变成：
[1,6]
左边界还是 1，右边界扩展到了 6。
6. 为什么合并完之后要 ans.add(new int[]{lef, rig})？
ans.add(new int[]{lef, rig});
因为当 while 循环结束时，说明：
-
当前区间已经不能再和后面的区间继续重叠
-
所以
[lef, rig]就是一个完整的、最终确定的合并结果
这时候就应该把它加入答案集中。
然后外层 for 循环继续往后走，再处理下一个尚未合并的新区间。
7. 为什么最后要用 toArray 转回二维数组？
return ans.toArray(new int[ans.size()][0]);
因为题目要求返回类型是：
int[][]
但我们在处理中使用的是更方便动态添加元素的：
List<int[]>
所以最后要把列表转成二维数组返回。
这是 Java 里处理这类题非常常见的一步。
手动模拟一遍
我们用最经典的例子来走一遍：
intervals = [[1,3],[2,6],[8,10],[15,18]]
第一步：排序
这一组本来就已经按左端点有序，所以排序后不变：
[[1,3],[2,6],[8,10],[15,18]]
第二步：处理第一个区间
当前：
lef = 1
rig = 3
看下一个区间 [2,6]：
-
2 <= 3，说明重叠
于是更新：
rig = max(3, 6) = 6
当前合并区间变成：
[1,6]
再看下一个区间 [8,10]：
-
8 > 6，说明不重叠
所以 [1,6] 已经合并完成，加入答案。
当前答案：
[[1,6]]
第三步：处理 [8,10]
当前：
lef = 8
rig = 10
看下一个区间 [15,18]：
-
15 > 10，不重叠
所以直接加入答案：
[[1,6],[8,10]]
第四步：处理 [15,18]
它后面没有区间了，所以也直接加入答案：
[[1,6],[8,10],[15,18]]
这就是最终结果。
再看一个边界相接的例子
例如：
intervals = [[1,4],[4,5]]
排序后不变。
当前区间：
[1,4]
看下一个区间 [4,5]：
-
4 <= 4，成立
说明这两个区间算重叠，可以合并。
更新：
rig = max(4,5) = 5
所以最终结果是：
[[1,5]]
这也是题目要求的答案。
为什么这个方法是正确的？
因为排序之后，所有区间按左端点从小到大排列。 这时对于任意一个区间：
-
如果它和后面的某个区间重叠，那么这个重叠关系一定会出现在“连续的一段区间”中
-
一旦出现某个区间不再重叠，后面更靠后的区间就更不可能和当前区间重叠了
所以我们只需要从左到右扫描，并不断维护当前合并区间 [lef, rig] 即可。
每次：
-
重叠就扩展右边界
-
不重叠就结算当前区间，开始新区间
这样既不会漏掉该合并的区间，也不会错误地把不该合并的区间放在一起。
复杂度分析
时间复杂度
主要分成两部分：
-
排序：
O(n log n)
-
扫描合并：
O(n)
所以总时间复杂度是：
O(n log n)
其中排序是主导部分。
空间复杂度
除了结果集之外，额外空间主要来自排序和存储答案。
如果只看算法本身的辅助变量，可以认为是：
O(1)
如果把结果集也算进去，则需要：
O(n)
这道题真正想考什么？
这道题表面上是在合并区间，但本质上考察的是一种非常重要的套路：
第一，区间题通常先排序
只要题目涉及：
-
区间重叠
-
区间合并
-
区间覆盖
第一反应通常都应该是：
能不能先排序？
排序之后，很多复杂关系会立刻变得简单。
第二，扫描过程中维护当前状态
这里维护的是当前合并区间 [lef, rig]。 这类“边遍历边更新状态”的做法，在数组题、区间题、贪心题里都非常常见。
所以这道题虽然不算难，但它非常有代表性。
和“插入区间”有什么关系？
这道题和后面的“插入区间”非常像。
合并区间
给你一组区间，要求把所有重叠区间合并。
插入区间
给你一组已经有序且不重叠的区间，再给一个新区间，要求插进去并合并。
两题本质上都在处理“区间重叠后如何更新边界”。 所以把这道题理解透，对后面的区间题会很有帮助。
总结
这道题的核心思想可以概括成一句话：
先按区间左端点排序，再从左到右扫描，把所有重叠的区间不断合并成一个更大的区间。
具体步骤就是：
-
先按区间起点排序
-
用
lef和rig记录当前正在合并的区间 -
如果下一个区间的左端点
<= rig，说明重叠，更新右端点 -
如果不重叠，就把当前区间加入答案，并开始处理新区间
-
最后返回所有合并结果
这样就能在：
O(n log n)
的时间复杂度内完成合并。
这是一道非常经典、也非常值得反复理解的区间题。 因为它会让你真正体会到：
-
排序为什么能降低问题复杂度
-
区间题为什么常常和贪心、扫描线思路结合出现
-
很多看似复杂的重叠关系，排序后都能用一次遍历解决
把这道题真正吃透之后，再去看：
-
插入区间
-
无重叠区间
-
用最少数量的箭引爆气球
-
会议室问题
这些区间类题目时，你会明显更容易抓住套路。
