AlgoViz Lab交互式算法学习Algorithms first
合并区间 · 交互式算法学习
合并所有重叠区间。
#56 · 区间
合并区间
Merge Intervals
intervals = [[1,3],[2,6],[8,10],[15,18]]区间轴8 个关键状态
步骤 1按左端点升序排列区间。
sorted推荐
排序后线性合并
时间
O(n log n)空间 O(n)按左端排序后，只需与结果中的最后一个区间比较。
1function merge(a) {2 a.sort((x, y) => x[0] - y[0]);3 const out = [];4 for (const cur of a) {5 const last = out.at(-1);6 if (last && cur[0] <= last[1]) last[1] = Math.max(last[1], cur[1]);7 else out.push([...cur]);8 }9 return out;10}多语言参考
来源 · CC BY-SA 4.0 ↗Java · C++ · Go
这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。
1class Solution {2 public int[][] merge(int[][] intervals) {3 Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));4 int st = intervals[0][0], ed = intervals[0][1];5 List<int[]> ans = new ArrayList<>();6 for (int i = 1; i < intervals.length; ++i) {7 int s = intervals[i][0], e = intervals[i][1];8 if (ed < s) {9 ans.add(new int[] {st, ed});10 st = s;11 ed = e;12 } else {13 ed = Math.max(ed, e);14 }15 }16 ans.add(new int[] {st, ed});17 return ans.toArray(new int[ans.size()][]);18 }19}交互式算法学习
从执行步骤真正理解 LeetCode 经典 150
本站整理 150 道高频算法面试题和 302 种解法。动画方法同步展示 JavaScript 与 Python；每题另提供 Java、C++ 与 Go 同题参考实现。
AlgoViz Lab
合并区间 · 解法对比
合并所有重叠区间。
- 测试用例
intervals = [[1,3],[2,6],[8,10],[15,18]]- 题目分类
- 区间
- 解法对比
- 2
反复寻找重叠对
找到任意重叠区间就合并，直到没有变化。
- 时间
O(n²)- 空间
O(n)
排序后线性合并
按左端排序后，只需与结果中的最后一个区间比较。
- 时间
O(n log n)- 空间
O(n)
为什么有效
按左端点排序后，若当前区间与结果末尾重叠，就只需延长末尾右端点；否则可以安全开始新区间。
关键不变量
out 始终互不重叠且按左端点有序，并等价覆盖所有已经扫描的区间。
易错点
- 端点相接也算重叠。
- 不要直接复用输入区间引用造成意外修改。
边界情况
- 空数组返回空数组。
- 只有一个区间时原样返回。
- 一个区间完全包含另一个区间。
更多案例
[[1,3],[2,6],[8,10],[15,18]][[1,6],[8,10],[15,18]]前两个区间合并。
[[1,4],[4,5]][[1,5]]端点相接视为重叠。
[[1,10],[2,3]][[1,10]]大区间包含小区间。