#56
中等
高频
排序合并区间
这是一道围绕数组展开的高频练习。建议先掌握「排序」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
数组
题目分析
给你若干个区间，每个区间由起点和终点组成。
如果两个区间有重叠，就把它们合并成一个更大的区间。最后返回所有合并后的结果。
一句话概括：
把有交集的区间连成一段，没有交集的就单独保留。
接下来怎么看推荐代码： 带着这个理解再看推荐代码时，重点观察这条主线：先按区间左端点排序，再顺序扫描，把能重叠的区间持续合并到当前结果尾部。
推荐代码
推荐解法：排序
时间复杂度： O(n log n)
空间复杂度： O(n)
核心思路： 先按区间左端点排序，再顺序扫描，把能重叠的区间持续合并到当前结果尾部。
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.ArrayList;
class Solution {
public int[][] merge(int[][] intervals) {
if (intervals.length == 0) {
return new int[0][2];
}
Arrays.sort(intervals, new Comparator<int[]>() {
public int compare(int[] interval1, int[] interval2) {
return interval1[0] - interval2[0];
}
});
List<int[]> merged = new ArrayList<int[]>();
for (int i = 0; i < intervals.length; ++i) {
int L = intervals[i][0], R = intervals[i][1];
if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
merged.add(new int[]{L, R});
} else {
merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
}
}
return merged.toArray(new int[merged.size()][]);
}
}结构化讲解
面试时怎么讲
开场思路
这题我会先排序，再线性扫描合并区间。
核心过程
- 按区间左端点排序，让相同重叠段自然靠在一起。
- 先把第一个区间放进结果，作为当前合并段。
- 依次比较当前区间和结果尾区间：重叠就扩右边界，不重叠就新开一个结果段。
- 扫描结束后，结果数组就是所有合并后的区间。
复杂度总结
时间复杂度 O(n log n)，空间复杂度 O(n)。
面试补一句：这题最值钱的一步不是合并，而是先排序建立局部比较关系。
核心思路
合并区间的关键在于先建立顺序。排序后，后面的区间只可能和结果里的最后一个区间发生关系，因此线性扫一遍就够了。
步骤讲解
1
先按左端点排序
让区间按照起点从小到大排列，保证后面扫描时处理顺序稳定。
为什么这样做：不排序就无法只看相邻关系，区间重叠判断会变复杂。
对应代码提示：Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
2
把第一个区间作为当前合并结果
结果数组先放入排序后的第一个区间，后续区间都尝试和它的尾部比较。
为什么这样做：排序后只需要维护“当前正在合并的最后一个区间”。
对应代码提示：merged.add(intervals[0]);
3
重叠就扩右边界，不重叠就新开一个区间
如果当前区间起点小于等于结果尾区间终点，就更新尾区间终点；否则直接追加新区间。
为什么这样做：排序后，当前区间不可能和更早的区间发生新的重叠关系。
对应代码提示：last[1] = Math.max(last[1], interval[1]);
易错点
没排序就直接扫
无序情况下，当前区间可能和前面任意区间重叠，线性扫描结论不成立。
正确理解：先按区间起点排序，再做单次扫描。
用严格小于判断重叠
像 [1,4] 和 [4,5] 这种边界相接也应该合并。
正确理解：判断条件写成
currentStart <= lastEnd。直接修改原区间后又复用引用
如果代码结构混乱，可能把结果中的区间状态改坏。
正确理解：要么新建结果区间，要么明确只更新结果尾部的右边界。
复杂度与适用判断
时间复杂度：O(n log n)
空间复杂度：O(n)
比其他方案更好在哪里：比两两尝试合并的暴力法清晰很多，也更容易证明不会漏区间。
适用判断：区间题只要涉及重叠、覆盖或并集，优先考虑“排序 + 扫描”。
额外提醒
- 排序后，当前区间只需要和结果尾部比较。
动画演示
如果你还没完全看懂，可以展开动画演示。
排序动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
排序动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
准备就绪 - 输入区间（用空格分隔，如：1,3 2,6 8,10 15,18），然后点击开始
合并步骤:
动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。