一、题目给定一个区间数组intervals[i] [starti, endi]要求合并所有重叠区间并返回一个互不重叠的区间数组。例如输入 [[1,3],[2,6],[8,10],[15,18]]输出[[1,6],[8,10],[15,18]]因为[1,3] 和 [2,6]发生重叠所以合并为[1,6]二、这道题最关键的一步先排序一开始这道题容易不知道从哪里入手。真正的突破口是先按照区间左端点从小到大排序。例如原始区间[[8,10],[1,3],[2,6]]排序以后[[1,3],[2,6],[8,10]]排序之后有一个非常重要的性质当前区间只需要和前面已经合并好的最后一个区间比较。因为所有区间的左端点已经递增后面的区间不可能重新跑到更前面去。因此问题就从“当前区间和前面所有区间比较”变成“当前区间只和 ans 最后一个区间比较”这就是整道题的核心优化思想。三、最终采用的代码import java.util.*; class Solution { public int[][] merge(int[][] intervals) { // 按照区间左端点升序排序 Arrays.sort( intervals, (a, b) - Integer.compare(a[0], b[0]) ); // 保存最终合并结果 Listint[] ans new ArrayList(); // 依次遍历每一个区间 for (int[] p : intervals) { int m ans.size(); // ans 不为空并且当前区间和最后一个区间重叠 if (m 0 p[0] ans.get(m - 1)[1]) { // 更新最后一个合并区间的右端点 ans.get(m - 1)[1] Math.max(ans.get(m - 1)[1], p[1]); } else { // 不重叠直接作为新区间加入答案 ans.add(p); } } // Listint[] 转换为 int[][] return ans.toArray(new int[ans.size()][]); } }这是我目前更推荐面试时使用的版本。四、第一步按照左端点排序代码Arrays.sort( intervals, (a, b) - Integer.compare(a[0], b[0]) );这里a b分别代表两个区间。例如a [1,3] b [8,10]那么a[0]就是1而b[0]就是8所以Integer.compare(a[0], b[0])就是按照区间第 0 个元素 也就是左端点进行升序排序。五、为什么用 Integer.compare有些答案会写Arrays.sort(intervals, (a, b) - a[0] - b[0]);这种写法通常也能通过。但更规范的是Integer.compare(a[0], b[0])因为a[0] - b[0]理论上可能发生整数溢出。所以面试时更推荐Arrays.sort(intervals, (a, b) - Integer.compare(a[0], b[0]));六、Listint[] ans是什么意思代码Listint[] ans new ArrayList();这里需要理解Listint[]表示List 里面每一个元素都是一个int[]。而每个区间刚好就是int[]例如[1,6]在 Java 中实际上可以表示为new int[]{1, 6}所以ans最终可能是[ [1,6], [8,10], [15,18] ]只是它此时的 Java 类型是Listint[]七、为什么不用 int[][] 直接保存答案因为合并之前我们不知道最终会有多少个区间。比如输入 10 个区间可能全部重叠 → 最终只有 1 个也可能全部不重叠 → 最终还是 10 个所以使用ArrayList这种可以动态扩容的集合更加方便。八、增强 for 循环代码for (int[] p : intervals) {表示依次取出intervals中的每一个区间当前区间保存到p中。例如intervals [ [1,3], [2,6], [8,10] ]那么遍历过程第一次 p [1,3] 第二次 p [2,6] 第三次 p [8,10]这里p[0]表示当前区间左端点。p[1]表示当前区间右端点。九、int m ans.size()int m ans.size();表示当前已经合并完成多少个区间。例如ans [ [1,6], [8,10] ]那么ans.size()就是2所以m 2十、ans.get(m - 1)为什么是最后一个区间Java List 下标从0开始。如果ans.size() 3那么三个元素下标0 1 2最后一个下标就是size - 1也就是m - 1所以ans.get(m - 1)表示ans 中最后一个区间。例如ans [ [1,6], [8,10] ]那么ans.get(1)就是[8,10]十一、为什么只需要和 ans 最后一个比较这是这版代码最重要的思想。因为已经按照左端点排序。例如ans [ [1,6], [8,10] ]当前p [9,15]只需要检查[8,10]因为[1,6]已经结束得更早。当前左端点9已经大于6所以不可能再和[1,6]合并。因此当前区间只需要和 ans 最后一个区间比较。十二、最核心的重叠判断代码if (m 0 p[0] ans.get(m - 1)[1]) {拆成两个条件。第一部分m 0意思ans 里面至少已经有一个区间。否则不能直接调用ans.get(m - 1)因为第一次m 0会变成ans.get(-1)显然不合法。第二部分p[0] ans.get(m - 1)[1]含义当前区间左端点 答案最后一个区间右端点说明两个区间发生重叠。例如最后一个区间 [1,6] 当前区间 [2,8]因为2 6所以重叠。十三、为什么不会导致 get(-1)Java 的具有短路特性。代码m 0 p[0] ans.get(m - 1)[1]如果m 0已经为falseJava 不会继续执行右边。所以第一次m 0不会真的执行ans.get(-1)这也是 Java 中短路与的典型使用场景。十四、重叠以后怎么合并代码ans.get(m - 1)[1] Math.max(ans.get(m - 1)[1], p[1]);例如最后一个区间 [1,6] 当前区间 [2,8]那么旧右端点 6 当前右端点 8更新Math.max(6, 8)得到8最终[1,6]变成[1,8]十五、为什么要 Math.max例如最后一个区间 [1,10] 当前区间 [2,5]当前区间完全包含在前一个区间中。如果直接right p[1];就会错误变成[1,5]因此必须Math.max(10,5)仍然得到10所以ans.get(m - 1)[1] Math.max(ans.get(m - 1)[1], p[1]);是标准写法。十六、为什么只更新右端点因为已经按照左端点升序排序。例如[1,6] [2,10]第二个区间左端点一定不会比第一个更小。所以合并[1,10]左端点1不用修改。只需要扩大右端点。十七、不重叠怎么办代码else { ans.add(p); }例如ans 最后一个 [1,6] 当前 [8,10]因为8 6所以不重叠。此时[1,6]已经不可能再被后面的区间影响。于是当前[8,10]直接作为一个新的合并区间加入ans.add(p);得到ans [ [1,6], [8,10] ]十八、第一次循环是怎么处理的一开始ans []第一个区间p [1,3]那么m ans.size();得到m 0判断m 0false。所以直接进入else执行ans.add(p);得到ans [[1,3]]所以这个版本不需要单独初始化start end这也是它比另一种写法更简洁的原因。十九、为什么这一版不用循环结束后再处理最后一个区间这是我学习过程中比较容易困惑的地方。另一种写法会自己维护start end例如int start intervals[0][0]; int end intervals[0][1];然后只有遇到新区间时才ans.add(new int[]{start,end});所以最后一个正在维护的区间可能还没有正式加入ans。因此需要循环结束后ans.add(new int[]{start,end});补一次。但是这一版不同。这一版对于每一个p都会立即做两种操作之一重叠 → 直接合并进 ans 最后一个区间 不重叠 → 直接 ans.add(p)也就是说每个区间在遍历过程中就已经进入了 ans 的状态。所以最后一个区间无论重叠还是不重叠都会在循环内部完成处理。因此不需要循环外额外补。可以简单记start/end 版本 延迟提交 → 最后需要补 ans 最后一个版本 边遍历边直接维护 ans → 不需要补二十、最后一行toArray代码return ans.toArray(new int[ans.size()][]);这是 Java 类型转换。当前ans类型Listint[]但题目要求int[][]所以需要转换Listint[] ↓ int[][]二十一、new int[ans.size()][]是什么假设ans.size() 3那么new int[ans.size()][]等于new int[3][]表示创建一个第一维长度为 3每一个位置未来放一个int[]的二维数组。可以暂时理解为[ null, null, null ]然后ans.toArray(...)把[1,6] [8,10] [15,18]放进去。最终得到int[][] result { {1,6}, {8,10}, {15,18} };二十二、完整执行过程输入[[1,3],[2,6],[8,10],[15,18]]排序后[[1,3],[2,6],[8,10],[15,18]]初始ans []第一次p [1,3] m 0无法比较。直接ans.add(p);得到ans [[1,3]]第二次p [2,6] m 1最后一个区间[1,3]判断2 3成立。所以右端点 max(3,6) 6得到ans [[1,6]]第三次p [8,10]最后一个[1,6]判断8 6false。所以ans.add(p);得到ans [ [1,6], [8,10] ]第四次p [15,18]最后一个[8,10]判断15 10false。加入ans [ [1,6], [8,10], [15,18] ]最后转换为int[][]返回。二十三、复杂度分析排序O(n log n)遍历O(n)所以总时间复杂度O(n log n)主要瓶颈是排序。结果集合最多存n个区间。二十四、面试讲法如果面试官让我讲可以这样回答我先按照所有区间的左端点进行升序排序。排序之后对于当前区间只需要判断它是否和结果集中最后一个区间重叠。如果当前区间左端点小于等于最后一个区间的右端点说明存在重叠此时更新最后一个区间的右端点为两个右端点的最大值。如果不重叠就直接把当前区间加入结果集合。由于每个区间在遍历时就已经被加入或合并到结果集合中所以循环结束以后不需要额外处理最后一个区间。排序时间复杂度为 O(n log n)遍历为 O(n)总体时间复杂度为 O(n log n)。二十五、这道题的通用思维以后看到区间 合并 重叠 覆盖第一反应可以考虑按照左端点排序排序以后经常会变成从左往右扫描 ↓ 只和前一个 / 当前合并区间比较这是一类非常常见的区间题套路。二十六、面试前 30 秒速记看到「合并区间」1. 按 start 排序 2. ans 保存合并结果 3. 当前区间 p 只和 ans 最后一个区间比较 4. 如果 p[0] last[1] 说明重叠 last[1] max(last[1], p[1]) 5. 否则 ans.add(p)代码模板Arrays.sort( intervals, (a, b) - Integer.compare(a[0], b[0]) ); Listint[] ans new ArrayList(); for (int[] p : intervals) { int m ans.size(); if (m 0 p[0] ans.get(m - 1)[1]) { ans.get(m - 1)[1] Math.max(ans.get(m - 1)[1], p[1]); } else { ans.add(p); } } return ans.toArray(new int[ans.size()][]);Java APIArrays.sort() 数组排序 Listint[] 保存多个 int[] 区间 ans.size() List 元素数量 ans.get(i) 获取第 i 个元素 ans.add(p) 添加元素 Math.max(a,b) 取较大值 toArray() List 转数组二十七、最终总结这道题真正需要记住的不是某一行 API而是区间不好直接处理 ↓ 先按照左端点排序 ↓ 区间关系变得有序 ↓ 当前区间只需要和最后一个合并区间比较排序以后每个新区间只有两种情况能合并 → 更新 ans 最后一个区间右端点 不能合并 → 直接加入 ans最终核心判断p[0] ans.get(m - 1)[1]核心更新ans.get(m - 1)[1] Math.max(ans.get(m - 1)[1], p[1]);这道题同时也顺带巩固了二维数组 增强 for Lambda 排序 Listint[] ArrayList get() size() add() Math.max() toArray() 短路 对于面试来说这是一道非常典型的排序 贪心扫描题目。以后遇到类似区间问题可以优先往这个方向思考。其他写法import java.util.*; class Solution { public int[][] merge(int[][] intervals) { Arrays.sort(intervals, (a, b) - Integer.compare(a[0], b[0])); Listint[] ans new ArrayList(); int start intervals[0][0]; int end intervals[0][1]; for (int i 1; i intervals.length; i) { int nextStart intervals[i][0]; int nextEnd intervals[i][1]; if (nextStart end) { end Math.max(end, nextEnd); } else { ans.add(new int[]{start, end}); start nextStart; end nextEnd; } } ans.add(new int[]{start, end}); return ans.toArray(new int[ans.size()][]); } }