示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本篇基于 doocs/leetcode 仓库中第 0056 号题解展开深入剖析「合并区间」这一经典区间类题目的完整解题链路先论证按左端点排序后只需一次扫描的核心观察再依次讲解三种实现端点滚动维护、答案末尾原地更新、按组合并并给出 Python、Java、C、Go、TypeScript、Rust、C#、JavaScript、Kotlin 共 9 种语言的完整可运行代码与源码对照。读完本文你将掌握区间重叠判定规则含边界相接与合并的通用套路并能直接迁移到日程合并、资源占用区间归并等实战场景。题目回顾以数组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] 可被视为重叠区间。示例 3输入intervals [[4,7],[1,4]] 输出[[1,7]] 解释区间 [1,4] 和 [4,7] 可被视为重叠区间。提示约束条件约束取值区间个数1 intervals.length 10^4单个区间长度intervals[i].length 2端点取值0 start_i end_i 10^4注意题目保证每个区间满足start_i end_i即不存在反向区间这为后续统一处理奠定了基础。核心观察为什么要先排序合并区间的难点在于重叠关系在无序时难以定位。若反复任取一个区间与其余区间两两合并最坏情况下时间复杂度为 O(n²)且合并顺序杂乱无章难以保证结果正确性而题目约束n 10^4O(n²) 的暴力做法在极限数据下偏紧。关键突破口在于排序按左端点排序后一个区间只会与当前尚未闭合的那段重叠后续区间的起点更大不可能跳过中间再叠回来。这句话是整道题的灵魂。以[[4,7],[1,4]]为例乱序时无法直接判断但按左端点排序后变成[[1,4],[4,7]]一眼可见两区间首尾相接。排序把全局两两比较降维成了与当前合并段的单次比较从而把复杂度从 O(n²) 降为 O(n log n)排序 O(n)扫描。方法一排序 一次遍历端点滚动维护思路详解这是最直观、也是仓库中默认给出的主流解法。思路如下将区间按左端点升序排序取出第一个区间的左右端点记为ststart与edend作为正在合并的区间依次遍历后续每个区间[s, e]若ed s说明当前正在合并的区间与新区间完全不相交注意是严格小于ed s视为重叠见示例 2于是把[st, ed]写入答案并让st, ed滚动到新区间否则说明二者重叠只需扩展右端点ed max(ed, e)遍历结束后把最后一对[st, ed]补充写入答案。用代码骨架表示intervals.sort() ans [] st, ed intervals[0] for s, e in intervals[1:]: if ed s: # 不重叠闭合当前段开启新段 ans.append([st, ed]) st, ed s, e else: # 重叠扩展右端点 ed max(ed, e) ans.append([st, ed])这一方案的优点是只维护一对端点变量、不回头修改已写入的答案逻辑清晰各语言实现高度一致。多语言实现Python3class Solution: def merge(self, intervals: List[List[int]]) - List[List[int]]: intervals.sort() ans [] st, ed intervals[0] for s, e in intervals[1:]: if ed s: ans.append([st, ed]) st, ed s, e else: ed max(ed, e) ans.append([st, ed]) return ansJavaclass Solution { public int[][] merge(int[][] intervals) { Arrays.sort(intervals, Comparator.comparingInt(a - a[0])); int st intervals[0][0], ed intervals[0][1]; Listint[] ans new ArrayList(); for (int i 1; i intervals.length; i) { int s intervals[i][0], e intervals[i][1]; if (ed s) { ans.add(new int[] {st, ed}); st s; ed e; } else { ed Math.max(ed, e); } } ans.add(new int[] {st, ed}); return ans.toArray(new int[ans.size()][]); } }Cclass Solution { public: vectorvectorint merge(vectorvectorint intervals) { sort(intervals.begin(), intervals.end()); int st intervals[0][0], ed intervals[0][1]; vectorvectorint ans; for (int i 1; i intervals.size(); i) { if (ed intervals[i][0]) { ans.push_back({st, ed}); st intervals[i][0]; ed intervals[i][1]; } else { ed max(ed, intervals[i][1]); } } ans.push_back({st, ed}); return ans; } };C 中vector自带字典序比较sort(intervals.begin(), intervals.end())会先按左端点、再按右端点排序正好符合需求。Gofunc merge(intervals [][]int) (ans [][]int) { sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] intervals[j][0] }) st, ed : intervals[0][0], intervals[0][1] for _, e : range intervals[1:] { if ed e[0] { ans append(ans, []int{st, ed}) st, ed e[0], e[1] } else if ed e[1] { ed e[1] } } ans append(ans, []int{st, ed}) return ans }注意 Go 版本在重叠分支里多了一个else if ed e[1]的判断只有当新区间右端点更大时才更新ed效果与max等价。TypeScriptfunction merge(intervals: number[][]): number[][] { intervals.sort((a, b) a[0] - b[0]); const ans: number[][] []; let [st, ed] intervals[0]; for (const [s, e] of intervals.slice(1)) { if (ed s) { ans.push([st, ed]); [st, ed] [s, e]; } else { ed Math.max(ed, e); } } ans.push([st, ed]); return ans; }Rustimpl Solution { pub fn merge(mut intervals: VecVeci32) - VecVeci32 { intervals.sort_unstable_by(|a, b| a[0].cmp(b[0])); let n intervals.len(); let mut res vec![]; let mut i 0; while i n { let l intervals[i][0]; let mut r intervals[i][1]; i 1; while i n r intervals[i][0] { r r.max(intervals[i][1]); i 1; } res.push(vec![l, r]); } res } }Rust 版本采用了sort_unstable_by不稳定排序原地进行无额外堆内存分配并以内层循环的方式一次性吞并整段重叠区间写法上已经与方法三趋同。C#public class Solution { public int[][] Merge(int[][] intervals) { intervals intervals.OrderBy(a a[0]).ToArray(); int st intervals[0][0], ed intervals[0][1]; var ans new Listint[](); for (int i 1; i intervals.Length; i) { if (ed intervals[i][0]) { ans.Add(new int[] { st, ed }); st intervals[i][0]; ed intervals[i][1]; } else { ed Math.Max(ed, intervals[i][1]); } } ans.Add(new int[] { st, ed }); return ans.ToArray(); } }JavaScript/** * param {number[][]} intervals * return {number[][]} */ var merge function (intervals) { intervals.sort((a, b) a[0] - b[0]); const result []; const n intervals.length; let i 0; while (i n) { const left intervals[i][0]; let right intervals[i][1]; while (true) { i; if (i n right intervals[i][0]) { right Math.max(right, intervals[i][1]); } else { result.push([left, right]); break; } } } return result; };Kotlinclass Solution { fun merge(intervals: ArrayIntArray): ArrayIntArray { intervals.sortBy { it[0] } val result mutableListOfIntArray() val n intervals.size var i 0 while (i n) { val left intervals[i][0] var right intervals[i][1] while (true) { i if (i n right intervals[i][0]) { right maxOf(right, intervals[i][1]) } else { result.add(intArrayOf(left, right)) break } } } return result.toTypedArray() } }以上 9 种实现均与仓库源码 Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.rs 等一一对应。复杂度分析时间复杂度 O(n × log n)排序主导空间复杂度 O(log n)原地排序所需的栈开销不计入结果数组。其中 n 为区间个数。方法二答案末尾原地更新思路详解方法一已经做到 O(n log n) 且正确但它额外维护了一对端点st, ed并且要等区间闭合时才写入答案遍历结束后还需再补写一次。方法二的改进点在于把当前正在合并的区间直接放在答案数组末尾。排序后先将第一个区间放入ans之后遍历每个区间[s, e]若ans末尾区间的右端点 s说明不重叠直接将该区间追加到末尾否则重叠原地更新末尾区间的右端点ans[-1][1] max(ans[-1][1], e)。这样既少了一组滚动变量也省去了遍历结束后的收尾写入。实现上的唯一注意点是原地修改答案数组末尾元素这一操作在不同语言中的写法差异见下方代码注释处。多语言实现Python3class Solution: def merge(self, intervals: List[List[int]]) - List[List[int]]: intervals.sort() ans [intervals[0]] for s, e in intervals[1:]: if ans[-1][1] s: ans.append([s, e]) else: ans[-1][1] max(ans[-1][1], e) return ansJavaclass Solution { public int[][] merge(int[][] intervals) { Arrays.sort(intervals, (a, b) - a[0] - b[0]); Listint[] ans new ArrayList(); ans.add(intervals[0]); for (int i 1; i intervals.length; i) { int s intervals[i][0], e intervals[i][1]; if (ans.get(ans.size() - 1)[1] s) { ans.add(intervals[i]); } else { ans.get(ans.size() - 1)[1] Math.max(ans.get(ans.size() - 1)[1], e); } } return ans.toArray(new int[ans.size()][]); } }Cclass Solution { public: vectorvectorint merge(vectorvectorint intervals) { sort(intervals.begin(), intervals.end()); vectorvectorint ans; ans.emplace_back(intervals[0]); for (int i 1; i intervals.size(); i) { if (ans.back()[1] intervals[i][0]) { ans.emplace_back(intervals[i]); } else { ans.back()[1] max(ans.back()[1], intervals[i][1]); } } return ans; } };Gofunc merge(intervals [][]int) (ans [][]int) { sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] intervals[j][0] }) ans append(ans, intervals[0]) for _, e : range intervals[1:] { if ans[len(ans)-1][1] e[0] { ans append(ans, e) } else { ans[len(ans)-1][1] max(ans[len(ans)-1][1], e[1]) } } return }TypeScriptfunction merge(intervals: number[][]): number[][] { intervals.sort((a, b) a[0] - b[0]); const ans: number[][] [intervals[0]]; for (let i 1; i intervals.length; i) { if (ans.at(-1)[1] intervals[i][0]) { ans.push(intervals[i]); } else { ans.at(-1)[1] Math.max(ans.at(-1)[1], intervals[i][1]); } } return ans; }C#public class Solution { public int[][] Merge(int[][] intervals) { intervals intervals.OrderBy(a a[0]).ToArray(); var ans new Listint[](); ans.Add(intervals[0]); for (int i 1; i intervals.Length; i) { if (ans[ans.Count - 1][1] intervals[i][0]) { ans.Add(intervals[i]); } else { ans[ans.Count - 1][1] Math.Max(ans[ans.Count - 1][1], intervals[i][1]); } } return ans.ToArray(); } }方法二的各语言实现对应仓库中的 Solution2.py、Solution2.java、Solution2.cpp、Solution2.go、Solution2.ts、Solution2.cs。方法一 vs 方法二小结维度方法一端点滚动方法二末尾原地更新维护变量额外st/ed一对端点直接复用答案末尾区间收尾处理遍历结束后需补写一次无需收尾代码规模稍长更简洁复杂度O(n log n) / O(log n)相同方法三按组合并内层循环一次性吞并思路详解方法二虽然避免了回头修改已写入的答案但循环逻辑仍是逐个判断、重叠则改写。方法三换一个角度按组合并。固定当前段的左端点l用内层循环把所有与它相交的区间依次吞并进来、不断拉大右端点r直到遇到第一个不相交的区间为止然后把[l, r]一次性写入答案。这样每一组合并段在写入前就已完整确定已写入的答案永远不会被再次改写逻辑上更加所见即所得。function merge(intervals: number[][]): number[][] { intervals.sort((a, b) a[0] - b[0]); const n intervals.length; const res []; let i 0; while (i n) { let [l, r] intervals[i]; i; while (i n r intervals[i][0]) { r Math.max(r, intervals[i][1]); i; } res.push([l, r]); } return res; }方法三的独立实现对应仓库中的 Solution3.ts。值得说明的是仓库中部分语言的默认解法本身也采用了内层循环合并整段的同构写法——例如方法一中的 Rust、JavaScript、Kotlin 实现Solution.rs其外层循环固定左端、内层 while 吞并所有r intervals[i][0]的重叠区间与方法三的核心思想完全一致。三种方法的统一视角把三种方法放在一起看它们的骨架完全相同1. 按左端点排序 2. 一次线性扫描 3. 遇到不重叠就闭合当前段遇到重叠就扩展右端点。区别仅在于当前段的状态存放在哪里方法一存放在独立变量中方法二存放在答案末尾元素中方法三存放在内层循环的局部变量中。三种写法时间复杂度一致读者可以根据语言习惯与代码可读性任选其一。边界情况与实现细节1. 区间首尾相接视为重叠示例 2 的关键判定语句是ed s严格小于才判定为不重叠因此[1,4]与[4,5]这类ed s的区间会被合并成[1,5]。这是本题最容易踩的坑若误写成ed s输出就会错误地多出一个区间。2. 单个区间当intervals.length 1时三种方法都能正确处理方法一在遍历循环不进入的情况下收尾把[st, ed]原样写出方法二直接返回[intervals[0]]方法三外层循环一次性写出。因此无需特判。3. 区间完全包含对于[1,10]与[2,3]排序后ed s成立进入重叠分支执行ed max(ed, e)由于e eded保持不变。max 运算天然兼容完全包含的情况这也是推荐用max而非直接赋值ed e的原因。4. 重复区间多个完全相同的区间如[2,4]出现三次排序后相邻第一次进入后ed不再变化后两次均被max吸收最终只输出一个[2,4]符合恰好覆盖输入中的所有区间的要求。5. 排序稳定性与原地修改Python 的intervals.sort()、C 的sort、Go 的sort.Slice、Rust 的sort_unstable_by均为原地排序Rust 明确为不稳定排序Java 的Arrays.sort对对象数组采用稳定排序。对本问题而言排序稳定性不影响正确性——因为合并结果只取决于区间端点的数值大小与相同左端点的区间先后顺序无关。上述实现全部原地修改输入数组intervals以完成排序若在需要保留原始数据的场景中调用应先在调用方复制一份再传入。复杂度总结方法时间复杂度空间复杂度思路关键词方法一O(n log n)O(log n)排序 端点滚动维护方法二O(n log n)O(log n)排序 答案末尾原地更新方法三O(n log n)O(log n)排序 按组合并内层循环其中 n 为区间个数空间复杂度为原地排序带来的栈开销未计入结果数组本身。三种方法均达到该问题的理论最优复杂度排序是必经步骤因此 O(n log n) 的下界无法突破。延伸区间问题的通用套路「排序 一次扫描」是区间类问题的地基性套路。在实际工程中日程合并、会议排期、资源占用区间归并等场景都遵循同样的思维路径先按某个维度排序把无规则的重叠关系转化为局部的顺序关系再用一次线性扫描完成合并或冲突检测。掌握第 56 题后后续遇到区间交集、区间差集、最大不重叠区间数等变体问题时都可以先回到排序 扫描这个原点重新组织思路。仓库资源导航本题的完整题解与多语言源码均位于仓库的solution/0000-0099/0056.Merge Intervals/目录下可直接查阅或对照学习中文题解README.md英文题解README_EN.md方法一源码Solution.py / Solution.java / Solution.cpp / Solution.go / Solution.ts / Solution.rs / Solution.cs / Solution.js / Solution.kt方法二源码Solution2.py / Solution2.java / Solution2.cpp / Solution2.go / Solution2.ts / Solution2.cs方法三源码Solution3.ts其中 Solution.py 与 Solution.java 是方法一的典型代表Solution2.go 是方法二的简洁示范Solution3.ts 则体现了方法三一次性吞并整段的写法可作为多语言对比与复习的最佳素材。赞分享示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐doocs/leetcode 题解深度解析56. 合并区间Merge Intervals的排序合并算法全解doocs/leetcode 题解深度解析56. 合并区间Merge Intervals的排序合并算法全解 区间合并是数组与排序类算法中最经典的实战模型之示例工程LeetCode-Go 题解精讲56. Merge Intervals 区间合并的排序与扫描算法LeetCode Go 题解精讲56. Merge Intervals 区间合并的排序与扫描算法 导读 本文基于开源仓库 LeetCode GoGo 语言实示例工程GHelper 风扇曲线 充电上限 GPU 模式华硕本轻量性能控制完整指南附参数表GHelper 风扇曲线 充电上限 GPU 模式华硕本轻量性能控制完整指南附参数表 只想把风扇调静音奥创中心却先弹一个更新窗口后台服务在托盘里桌面应用上一篇UB组件部署自动化ub-pkg-manager与systemd服务联动最佳实践下一篇深入理解openEuler/os-compat-analyzer内核符号比对CRC冲突如何影响系统稳定性创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考