普通数组

合并区间

中等#56Java时间 O(n log n)空间 O(n),输出

题目要做什么

合并所有有重叠的闭区间,返回互不重叠的区间列表。端点相同也算重叠。

题目示例输入intervals = [[1,3],[2,6],[8,10],[15,18]]
题目示例输出[[1,6],[8,10],[15,18]]

01 为什么这样做

先按起点排序。若新区间的起点在最后一个结果区间内,就扩展最后的右端点;否则新增区间。

始终成立的条件

结果区间按起点递增且互不重叠;最后一个结果区间吸收所有已扫描的重叠区间。

02 看见算法执行

动画与代码同步

修改输入,播放自己的例子

当前使用题目示例
修改输入会改变执行过程;预期输出用于核对结果。
数组 / nums步骤 1
执行状态
本次演示输出播放到最后查看

Solution.java参考解法
1class Solution {2    public int[][] merge(int[][] intervals) {3        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));4        List<int[]> ans = new ArrayList<>();5        for (int[] current : intervals) {6            if (ans.isEmpty() || ans.get(ans.size() - 1)[1] < current[0]) {7                ans.add(current.clone());8            } else {9                int[] last = ans.get(ans.size() - 1);10                last[1] = Math.max(last[1], current[1]);11            }12        }13        return ans.toArray(new int[0][]);14    }15}

键盘控制:A 后退 · D 前进

编程练习

↑↓ 选择↵ 打开Pagefind 全文检索