56. 合并区间
目录
题目链接：
题目：
解题思路：
代码：
总结：
题目链接：
56. 合并区间 - 力扣（LeetCode）
题目：
56. 合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [start_i, end_i] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
示例 1:
输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠，将它们合并为 [1,6]。
示例 2:
输入: intervals = [[1,4],[4,5]]
输出: [[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
提示:
1 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= start_i <= end_i <= 10^4
解题思路：
先按照左边进行升序排序,然后比较相邻右边,若当前左边大于前一个相邻的右边,那就直接赋值给新数组，否则扩展当前数组的右边
代码：
class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals,(v1,v2)->v1[0]-v2[0]);int [][] res=new int[intervals.length][2];int idx=-1;for(int[] interval:intervals){if(idx==-1||interval[0]>res[idx][1]){res[++idx]=interval;}else{res[idx][1]=Math.max(res[idx][1],interval[1]);}}return Arrays.copyOf(res,idx+1);}
}以下从问题背景、算法流程、代码逐行拆解、核心细节、优缺点、扩展对比等维度，深度解析这段合并区间的代码，帮你彻底吃透逻辑（预计超 2000 字 ）：
一、问题背景：为什么需要合并区间？
在实际开发中（比如日历预约、区间覆盖计算），经常需要把重叠或相邻的区间合并，得到简洁的无重叠区间集合。
LeetCode 第 56 题要求：输入若干区间（如 [[1,3],[2,6]]），输出合并后的结果（[[1,6]]）—— 这段代码完美解决了这个问题。
二、整体思路：排序 + 贪心
合并区间的核心逻辑是 “先排序，再合并”：
排序：按区间的起始点升序排列（确保从左到右处理区间）。
贪心合并：遍历排序后的区间，维护一个 “当前合并区间”，遇到不重叠的新区间就新增，遇到重叠的就扩展当前区间的右端点。
三、代码逐行拆解（核心逻辑）
类与方法定义
java
运行
class Solution {
public int[][] merge(int[][] intervals) {
Solution 是 LeetCode 解题类，merge 是题目要求的方法，入参是二维数组 intervals（每个子数组是 [start, end]），返回合并后的二维数组。
1. 排序区间（关键第一步）
java
运行
Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
作用：按区间的起始值 v1[0] 升序排序。
比如输入 [[2,6],[1,3]]，排序后变成 [[1,3],[2,6]]—— 确保我们从左到右处理区间，这是 “贪心合并” 的基础。
底层原理：
Arrays.sort 的第二个参数是 Comparator（比较器），v1[0] - v2[0] 是简化写法（等价于 (a, b) -> a - b 的升序）。若结果为负，v1 排在 v2 前；为正则相反。
2. 初始化结果数组与指针
java
运行
int[][] res = new int[intervals.length][2];
int idx = -1;
res：存储合并后的区间，初始长度与原数组相同（最多不会超过原长度，最后会截断）。
idx：结果数组的当前填充索引（初始 -1 表示还未填充任何区间）。
3. 遍历区间，贪心合并（核心逻辑）
java
运行
for (int[] interval : intervals) {
if (idx == -1 || interval[0] > res[idx][1]) {
res[++idx] = interval;
} else {
res[idx][1] = Math.max(res[idx][1], interval[1]);
}
}
这是代码的灵魂，逐行拆解：
情况 1：idx == -1（结果数组为空，首次填充）
当 idx == -1 时，说明还没有任何合并后的区间。直接将当前区间 interval 放入 res[0]，并让 idx 从 -1 变为 0。
情况 2：interval[0] > res[idx][1]（新区间不重叠，新增）
若当前遍历的区间 interval 的起始点 > 结果数组中最后一个区间的结束点（res[idx][1]），说明无重叠，需要新增区间。
例如：结果数组最后一个区间是 [1,3]，当前区间是 [4,5] → 4 > 3，直接新增 [4,5] 到结果数组。
情况 3：else（区间重叠，扩展右端点）
若当前区间的起始点 ≤ 结果数组最后一个区间的结束点，说明有重叠，需要合并。
合并逻辑：取两个区间右端点的最大值，更新结果数组中最后一个区间的右端点。
例如：结果数组最后一个区间是 [1,3]，当前区间是 [2,6] → 合并为 [1,6]（res[idx][1] = max(3,6) = 6）。
4. 截断结果数组（返回实际长度）
java
运行
return Arrays.copyOf(res, idx + 1);
作用：因为 res 初始长度是 intervals.length（可能有冗余空间），而实际合并后的区间数量是 idx + 1（idx 从 0 开始计数），所以用 Arrays.copyOf 截断到实际长度。
例如：原数组长度是 4，合并后只有 2 个区间 → 返回前 2 个元素。
四、核心细节：为什么这么写？
1. 排序的必要性
如果不排序，区间可能是乱序的（比如 [[5,6],[1,3]]），直接合并会漏掉重叠情况。
排序后确保 “前面的区间起始点 ≤ 后面的”，保证贪心策略的正确性（每次只需要和最后一个合并后的区间比较）。
2. 贪心策略的逻辑
贪心的本质是 “局部最优推导全局最优”：
每次遇到不重叠的区间就新增，遇到重叠的就扩展 —— 最终得到的无重叠区间集合，就是全局最优解（所有重叠都被合并）。
3. Arrays.copyOf 的作用
res 初始分配了最大可能的空间（intervals.length），但实际合并后的区间数量可能更少（比如所有区间都重叠，结果只有 1 个区间）。
Arrays.copyOf 会创建一个新数组，长度为 idx + 1，只保留前 idx + 1 个元素，避免返回冗余的空区间。
4. 区间合并的边界条件
相邻区间是否合并？比如 [[1,4],[4,5]] → 代码中 interval[0] == res[idx][1]（4 == 4），会进入 else 分支，合并为 [1,5]—— 符合题目要求（相邻视为重叠）。
空输入？题目约束 intervals.length >=1，无需处理 null。
五、优缺点分析
优点：
时间复杂度优秀：
排序的时间复杂度是 O(n log n)（n 是区间数量），遍历是 O(n) → 整体 O(n log n)，是该问题的最优复杂度（排序无法避免）。
空间复杂度合理：
排序的空间复杂度是 O(log n)（递归栈或排序算法的临时空间），res 是 O(n) → 整体 O(n)。
逻辑简洁：
排序 + 一次遍历 + 贪心合并，代码行数少，思路清晰。
缺点（几乎没有，硬找的话 ）：
依赖 Java 的 Arrays.sort 和 Arrays.copyOf，如果在不允许使用这些工具类的场景（比如纯手写算法），需要自己实现排序和数组截断 —— 但实际开发 / 面试中，用工具类是更优解。
六、测试用例验证
测试用例 1：普通重叠
输入：[[1,3],[2,6],[8,10],[15,18]]
排序后：[[1,3],[2,6],[8,10],[15,18]]
合并过程：
idx=-1 → 新增 [1,3]（idx=0）。
下一个区间 [2,6]：2 <=3 → 合并为 [1,6]（res[0][1]=6）。
下一个区间 [8,10]：8>6 → 新增（idx=1）。
下一个区间 [15,18]：15>10 → 新增（idx=2）。
结果：[[1,6],[8,10],[15,18]]（符合预期）。
测试用例 2：相邻区间
输入：[[1,4],[4,5]]
排序后：[[1,4],[4,5]]
合并过程：
新增 [1,4]（idx=0）。
下一个区间 [4,5]：4 <=4 → 合并为 [1,5]（res[0][1]=5）。
结果：[[1,5]]（符合预期）。
测试用例 3：无重叠
输入：[[1,2],[3,4],[5,6]]
排序后：[[1,2],[3,4],[5,6]]
合并过程：每个区间都不重叠，直接新增。
结果：[[1,2],[3,4],[5,6]]（符合预期）。
七、与其他解法对比
解法 2：链表存储（低效版）
用链表动态存储合并后的区间，每次遍历都检查所有已存在的区间是否重叠 —— 时间复杂度 O(n²)（最坏情况），远不如排序 + 贪心的 O(n log n)。
解法 3：递归（不实用）
递归实现区间合并，会因栈深度（区间数量）过大导致栈溢出，且代码复杂，不如迭代直观。
八、扩展：如何处理 “区间删除”？
如果题目扩展为 “删除某些区间后再合并”，可以：
先标记要删除的区间（或过滤掉）；
对剩余区间执行相同的 “排序 + 贪心合并” 逻辑。
这段代码的 “排序 + 遍历合并” 模式，是处理区间问题的基础框架，可灵活扩展。
总结
这段代码的核心是 “排序奠定顺序，贪心实现合并”：
排序让区间按起始点有序，保证合并逻辑的简单性；
贪心策略通过 “新增或扩展” 两种操作，高效得到无重叠区间；
Arrays.copyOf 优雅地处理了结果数组的截断，避免冗余。
它不仅解决了 LeetCode 问题，更传递了 “排序 + 贪心” 这类经典算法模式的思想 —— 很多区间相关的问题（如插入区间、区间交集）都可以用类似思路解决。
如果你在面试中写出这段代码，面试官能看到你对算法复杂度的把控（O(n log n) 是最优解）、贪心策略的理解（局部最优到全局最优），以及代码简洁性的追求 —— 这就是高质量算法题解的价值。
总结：
本文详细解析了LeetCode第56题"合并区间"的解题思路与代码实现。通过排序+贪心策略，先按区间起始点排序，再遍历合并重叠区间。核心代码先排序，再维护结果数组，根据区间是否重叠决定新增或合并。时间复杂度O(nlogn)，空间复杂度O(n)。文章从问题背景、算法流程、代码解析、测试用例等多个维度展开，并对比了其他解法，最后总结出这种"排序+贪心"模式是解决区间类问题的通用框架，具有较高的算法教学价值。4