难度：中等 | 面试频率：⭐⭐⭐⭐
📝 题目描述
以数组intervals表示若干个区间的集合，其中单个区间为intervals[i] = [start_i, end_i]。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
示例
示例 1：
text
输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠，将它们合并为 [1,6]。
示例 2：
text
输入：intervals = [[1,4],[4,5]] 输出：[[1,5]] 解释：区间 [1,4] 和 [4,5] 被视为重叠区间（端点接触就算重叠）。
提示
1 <= intervals.length <= 10^4intervals[i].length == 20 <= start_i <= end_i <= 10^4
🎯 解题思路
核心思想
排序 + 贪心合并
合并区间的本质：
如果两个区间有重叠（或端点相接），它们可以合并成一个更大的区间
合并后的区间 =
[min(左边界), max(右边界)]
算法步骤
排序：按照区间的左端点升序排序
初始化：将第一个区间加入结果集
遍历：对于每个后续区间，判断是否与结果集中最后一个区间重叠
重叠：更新最后一个区间的右端点（取最大值）
不重叠：直接加入结果集
💻 完整代码
java
class Solution { public int[][] merge(int[][] intervals) { // 边界情况 if (intervals == null || intervals.length <= 1) { return intervals; } // 1. 按照区间左端点升序排序 Arrays.sort(intervals, (a, b) -> a[0] - b[0]); // 2. 用 List 存储合并后的结果 List<int[]> merged = new ArrayList<>(); // 3. 初始化：先把第一个区间放进去 int[] current = intervals[0]; merged.add(current); // 4. 遍历后续区间 for (int i = 1; i < intervals.length; i++) { int[] interval = intervals[i]; int currentEnd = current[1]; int nextStart = interval[0]; int nextEnd = interval[1]; // 判断是否重叠：当前区间的右端点 >= 下一个区间的左端点 if (currentEnd >= nextStart) { // 重叠！合并：更新当前区间的右端点 current[1] = Math.max(currentEnd, nextEnd); } else { // 不重叠：添加新区间 current = interval; merged.add(current); } } // 5. List 转数组返回 return merged.toArray(new int[merged.size()][]); } }🔍 代码详解
1. 排序（关键第一步）
java
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
按照每个区间的起点从小到大排序
排序后，只需要和前一个区间比较，不需要和所有区间比较
为什么排序很重要？
text
排序前：[[2,6], [1,3]] → 无法直接判断 排序后：[[1,3], [2,6]] → 一目了然：1->3 和 2->6 重叠
2. 合并逻辑
重叠的判断条件：
text
当前区间的右端点 >= 下一个区间的左端点
图示：
text
重叠情况： [1 3] [2 6] → 3 >= 2，重叠 合并后：[1 6] 不重叠情况： [1 3] [4 6] → 3 < 4，不重叠 结果：[[1,3], [4,6]] 边界重叠（也算重叠）： [1 4] [4 6] → 4 >= 4，重叠 合并后：[1 6]
3. 原地更新技巧
java
int[] current = intervals[0]; merged.add(current);
注意：merged.add(current)添加的是引用，后续修改current[1]会直接修改 merged 中的元素，不需要重新添加。
🖼️ 图解示例
示例：[[1,3],[2,6],[8,10],[15,18]]
步骤 1：排序（已经有序）
text
[1,3] [2,6] [8,10] [15,18]
步骤 2：初始化
text
merged = [[1,3]] current = [1,3]
步骤 3：处理 [2,6]
text
current = [1,3], 下一个 = [2,6] 判断：3 >= 2 → 重叠 合并：current[1] = max(3, 6) = 6 merged = [[1,6]]
步骤 4：处理 [8,10]
text
current = [1,6], 下一个 = [8,10] 判断：6 >= 8 ? 否（6 < 8）→ 不重叠 添加新区间：current = [8,10], merged = [[1,6], [8,10]]
步骤 5：处理 [15,18]
text
current = [8,10], 下一个 = [15,18] 判断：10 >= 15 ? 否 → 不重叠 添加新区间：current = [15,18], merged = [[1,6], [8,10], [15,18]]
最终结果
text
[[1,6], [8,10], [15,18]]
📊 复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 排序 | O(n log n) | O(log n)（快排栈空间） |
| 遍历合并 | O(n) | O(1)（不计输出） |
| 总计 | O(n log n) | O(log n)~ O(n) |
✅ 测试验证
java
public static void main(String[] args) { Solution solution = new Solution(); // 示例 1 int[][] intervals1 = {{1,3},{2,6},{8,10},{15,18}}; int[][] result1 = solution.merge(intervals1); printResult(result1); // [[1,6],[8,10],[15,18]] // 示例 2（边界重叠） int[][] intervals2 = {{1,4},{4,5}}; int[][] result2 = solution.merge(intervals2); printResult(result2); // [[1,5]] // 完全包含 int[][] intervals3 = {{1,10},{2,3},{4,5},{6,7}}; int[][] result3 = solution.merge(intervals3); printResult(result3); // [[1,10]] // 无需合并 int[][] intervals4 = {{1,2},{3,4},{5,6}}; int[][] result4 = solution.merge(intervals4); printResult(result4); // [[1,2],[3,4],[5,6]] } private static void printResult(int[][] intervals) { System.out.print("["); for (int i = 0; i < intervals.length; i++) { System.out.print("[" + intervals[i][0] + "," + intervals[i][1] + "]"); if (i < intervals.length - 1) System.out.print(","); } System.out.println("]"); }💡 关键点总结
| 要点 | 说明 |
|---|---|
| 必须排序 | 按左端点排序，保证每次只需和上一个区间比较 |
| 重叠条件 | 当前右端点 >= 下一个左端点 |
| 合并操作 | 右端点取max(当前右, 下一个右) |
| 边界处理 | 端点相接（如[1,4]和[4,5]）也算重叠 |
| 原地修改 | 使用引用，避免重复创建数组 |
⚠️ 常见错误
错误 1：忘记排序
java
// ❌ 错误：没有排序直接合并 // 输入 [[2,6],[1,3]] 会失败 // ✅ 正确：先排序 Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
错误 2：重叠条件写错
java
// ❌ 错误：没有考虑相等的情况 if (currentEnd > nextStart) // 漏掉了相等的情况 // ✅ 正确：包含相等 if (currentEnd >= nextStart)
错误 3：合并时忘记更新右端点最大值
java
// ❌ 错误：直接赋值 current[1] = nextEnd; // ✅ 正确：取最大值 current[1] = Math.max(currentEnd, nextEnd);
🎓 举一反三
相关题目
| 题目 | 难度 | 解法要点 |
|---|---|---|
| 57. 插入区间 | 中等 | 先插入再合并，或直接遍历 |
| 435. 无重叠区间 | 中等 | 贪心：按右端点排序 |
| 452. 用最少数量的箭引爆气球 | 中等 | 区间重叠的变种 |
| 986. 区间列表的交集 | 中等 | 双指针遍历两个区间列表 |
变形：返回合并后的区间数量
java
public int countMerged(int[][] intervals) { if (intervals.length == 0) return 0; Arrays.sort(intervals, (a, b) -> a[0] - b[0]); int count = 1; int currentEnd = intervals[0][1]; for (int i = 1; i < intervals.length; i++) { if (currentEnd >= intervals[i][0]) { currentEnd = Math.max(currentEnd, intervals[i][1]); } else { count++; currentEnd = intervals[i][1]; } } return count; }📌 面试技巧
面试官可能会问：
Q：如果区间列表非常大（10^6 个区间），你的算法还能用吗？
A：排序 O(n log n) 是瓶颈，10^6 个区间排序约需 2×10^7 次比较，现代计算机可以接受。如果内存不够，可以用外部排序。
Q：能否不用排序？
A：可以构建线段树或区间树，但复杂度更高（O(n log C)），且实现复杂，不如排序简单高效。
Q：端点相接算重叠吗？
A：题目示例
[1,4]和[4,5]合并为[1,5]，说明算重叠。
🔗 相关链接
LeetCode 原题：56. 合并区间
LeetCode 官方题解：合并区间官方题解
💬 欢迎在评论区讨论交流！如果这篇文章对你有帮助，请点赞支持～
📢 关注我，持续更新 LeetCode Hot 100 题解！
