教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本篇题解基于 AlgoNote「算法通关手册」的 0056. 合并区间题解系统讲解「数组 排序」类高频中等题先对区间按左端点排序再在一次线性扫描中贪心地合并所有重叠区间。读完本文你将掌握区间合并问题的标准解法模板、复杂度推导与边界情况处理并能将其迁移到插入区间、无重叠区间等系列变体题目中。题目概述题目0056. 合并区间Merge Intervals标签为「数组、排序」难度中等。描述给定数组intervals表示若干个区间的集合其中单个区间为intervals[i] [starti, endi]。要求合并所有重叠的区间并返回一个不重叠的区间数组该数组需恰好覆盖输入中的所有区间。数据范围说明来自原题解文档$1 \le intervals.length \le 10^4$$intervals[i].length 2$$0 \le starti \le endi \le 10^4$。示例 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] 可被视为重叠区间。从示例 2 可以看出题目将「首尾相接」的区间前一个区间的右端点恰好等于后一个区间的左端点即end1 start2也视为重叠合并条件为前一个区间的右端点 当前区间的左端点。解题思路排序 单次扫描贪心合并这是区间类问题中最经典的解法模板。核心洞察在于无序的区间集合很难判断重叠关系但一旦按左端点排序重叠判断就变成了一次线性扫描。算法步骤排序设定数组ans用于表示最终不重叠的区间数组先对原始区间按照区间左端点大小从小到大进行排序。初始化将第一个区间加入ans数组中此时ans中只有一个区间天然不重叠。遍历合并依次考虑后续的每一个区间如果第i个区间的左端点大于前一个区间即ans中最后一个区间的右端点说明这两个区间不会重合直接将该区间加入ans数组否则说明这两个区间重合比较两个区间的右端点值将前一个区间的右端点更新为两者中的较大值然后继续考虑下一个区间以此类推。返回结果遍历结束后ans中即为合并后的不重叠区间数组直接返回。这里的贪心本质是由于已按左端点升序排列后出现的区间左端点只会更大因此每个区间至多需要与「当前合并链」中的最后一个区间比较一次无需回溯从而保证单次扫描即可完成。代码实现思路 1class Solution: def merge(self, intervals: List[List[int]]) - List[List[int]]: intervals.sort(keylambda x: x[0]) ans [] for interval in intervals: if not ans or ans[-1][1] interval[0]: ans.append(interval) else: ans[-1][1] max(ans[-1][1], interval[1]) return ans对代码的关键行逐条拆解intervals.sort(keylambda x: x[0])按区间左端点升序排序。key指定排序依据为每个区间的第 0 个元素左端点这保证了后续遍历时重叠判断只与相邻区间有关if not ans or ans[-1][1] interval[0]ans为空首元素或当前区间左端点严格大于ans最后一个区间的右端点时二者无重叠直接追加ans[-1][1] max(ans[-1][1], interval[1])否则发生重叠将ans最后一个区间的右端点扩展为二者右端点的较大值完成合并。值得注意的是上述写法中ans[-1]直接引用的是已加入的列表对象因此直接修改ans[-1][1]就能同步更新结果数组无需弹出再插入代码更简洁高效。复杂度分析时间复杂度$O(n \times \log_2 n)$其中 $n$ 为区间数量。瓶颈在于排序排序完成后的合并遍历仅需 $O(n)$。空间复杂度$O(n)$。结果数组ans最多与输入区间数量同量级全部不重叠时。为什么排序是解题的关键前提本题标签为「数组、排序」排序步骤不是可有可无的辅助而是整个算法成立的前提。AlgoNote 在 数组排序 一章中系统梳理了排序算法的分类与选择策略按时间复杂度可分为 $O(n^2)$ 的简单排序、$O(n \log n)$ 的高级排序快速、归并、堆与 $O(n)$ 的线性排序。本题采用的正是 $O(n \log n)$ 级别的排序配合 $O(n)$ 线性扫描整体达到区间合并问题的最优量级。关于排序的具体实现仓库的 快速排序源码 展示了本手册中排序算法的工程化写法通过哨兵划分partition将数组以基准数为界分成左右两部分再递归对子数组排序。本题解法中使用 Python 内置的list.sort()基于 Timsort稳定、原地即可满足需求你也可自行替换为手册中的任意排序实现来加深理解。边界情况与易错点分析单个区间intervals [[1,2]]时首个区间直接加入ans循环结束返回[[1,2]]无需特殊处理。首尾相接视为重叠[[1,4],[4,5]]中ans[-1][1] interval[0] 4不满足ans[-1][1] interval[0]走合并分支得到[1,5]。判断条件必须使用严格小于而不是这正是示例 2 考察的细节。完全包含关系[[1,10],[2,3]]中[2,3]被[1,10]完全包含合并后右端点取max(10, 3) 10区间不变结果正确。连续多段重叠[[1,3],[2,6],[8,10],[15,18]]中[1,3]与[2,6]合并为[1,6][8,10]因6 8不重叠直接加入[15,18]同理得到[[1,6],[8,10],[15,18]]。坐标非负题目约束 $0 \le starti \le endi$因此可用ans[-1][1] interval[0]这一简洁比较若坐标可能出现负数逻辑依然成立无需改动。同类题延伸区间问题的三步曲「排序 线性扫描」是区间类问题Interval Problems的通用骨架。AlgoNote 题解库中与之直接相关的题目还有0057. 插入区间输入区间本身已按左端点有序给定newInterval插入并合并。其解法将遍历分为三个阶段左侧完全不相交的区间直接加入、与新区间重叠的部分就地合并min/max扩展端点、右侧完全不相交的区间追加时间复杂度为 $O(n)$。可视为「合并区间」在已排序输入上的单次插入变体0435. 无重叠区间要求移除最少的区间使剩余区间互不重叠。其贪心策略改为按右端点排序每次选择结束最早的区间用end_pos intervals[i][0]判断是否新增不重叠区间最终答案为len(intervals) - count。与本题「按左端点排序 合并」形成鲜明对照体现了同一数据结构下排序依据的选择对解法的决定性影响。可见区间问题通常遵循三步曲确定排序依据左端点或右端点→ 线性扫描 → 按重叠条件合并或取舍。掌握了 0056. 合并区间 的基础模板再遇到同类题目时就能快速套用。总结本题在 AlgoNote 手册中被收录于「数组排序算法题目」分类见 分类刷题列表是数组 排序结合考查的代表题。其核心结论可归纳为按左端点排序后重叠判断退化为相邻区间的比较单次 $O(n)$ 扫描即可完成合并合并时右端点取max保证「恰好覆盖输入中的所有区间」整体时间复杂度 $O(n \log n)$、空间复杂度 $O(n)$是区间合并问题的最优级解。建议动手运行示例代码验证两个示例的输出并尝试用「按右端点排序」的变体重写本题体会排序依据变化带来的行为差异这将对后续攻克区间类系列题目大有裨益。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode-Go 题解精讲56. Merge Intervals 区间合并的排序与扫描算法LeetCode Go 题解精讲56. Merge Intervals 区间合并的排序与扫描算法 导读 本文基于开源仓库 LeetCode GoGo 语言实示例工程合并区间排序与贪心算法的区间合并合并区间排序与贪心算法的区间合并 问题引入 在处理时间安排、日程管理、资源分配等实际问题时我们经常会遇到区间重叠的情况。例如 会议安排系统需要合并重叠的会示例工程教程LeetCode 56 合并区间Merge Intervals全解从排序到扫描线一次吃透区间重叠合并算法LeetCode 56 合并区间Merge Intervals全解从排序到扫描线一次吃透区间重叠合并算法 导读 合并区间Merge Intervals示例工程教程上一篇【亲测免费】 clklog构建用户画像的强大工具下一篇NiGui未来路线图即将到来的macOS支持与新特性预览创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LeetCode 0056 合并区间（Merge Intervals）题解：排序 + 贪心合并思路精讲 | AlgoNote 算法通关手册
教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本篇题解基于 AlgoNote「算法通关手册」的 0056. 合并区间题解系统讲解「数组 排序」类高频中等题先对区间按左端点排序再在一次线性扫描中贪心地合并所有重叠区间。读完本文你将掌握区间合并问题的标准解法模板、复杂度推导与边界情况处理并能将其迁移到插入区间、无重叠区间等系列变体题目中。题目概述题目0056. 合并区间Merge Intervals标签为「数组、排序」难度中等。描述给定数组intervals表示若干个区间的集合其中单个区间为intervals[i] [starti, endi]。要求合并所有重叠的区间并返回一个不重叠的区间数组该数组需恰好覆盖输入中的所有区间。数据范围说明来自原题解文档$1 \le intervals.length \le 10^4$$intervals[i].length 2$$0 \le starti \le endi \le 10^4$。示例 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] 可被视为重叠区间。从示例 2 可以看出题目将「首尾相接」的区间前一个区间的右端点恰好等于后一个区间的左端点即end1 start2也视为重叠合并条件为前一个区间的右端点 当前区间的左端点。解题思路排序 单次扫描贪心合并这是区间类问题中最经典的解法模板。核心洞察在于无序的区间集合很难判断重叠关系但一旦按左端点排序重叠判断就变成了一次线性扫描。算法步骤排序设定数组ans用于表示最终不重叠的区间数组先对原始区间按照区间左端点大小从小到大进行排序。初始化将第一个区间加入ans数组中此时ans中只有一个区间天然不重叠。遍历合并依次考虑后续的每一个区间如果第i个区间的左端点大于前一个区间即ans中最后一个区间的右端点说明这两个区间不会重合直接将该区间加入ans数组否则说明这两个区间重合比较两个区间的右端点值将前一个区间的右端点更新为两者中的较大值然后继续考虑下一个区间以此类推。返回结果遍历结束后ans中即为合并后的不重叠区间数组直接返回。这里的贪心本质是由于已按左端点升序排列后出现的区间左端点只会更大因此每个区间至多需要与「当前合并链」中的最后一个区间比较一次无需回溯从而保证单次扫描即可完成。代码实现思路 1class Solution: def merge(self, intervals: List[List[int]]) - List[List[int]]: intervals.sort(keylambda x: x[0]) ans [] for interval in intervals: if not ans or ans[-1][1] interval[0]: ans.append(interval) else: ans[-1][1] max(ans[-1][1], interval[1]) return ans对代码的关键行逐条拆解intervals.sort(keylambda x: x[0])按区间左端点升序排序。key指定排序依据为每个区间的第 0 个元素左端点这保证了后续遍历时重叠判断只与相邻区间有关if not ans or ans[-1][1] interval[0]ans为空首元素或当前区间左端点严格大于ans最后一个区间的右端点时二者无重叠直接追加ans[-1][1] max(ans[-1][1], interval[1])否则发生重叠将ans最后一个区间的右端点扩展为二者右端点的较大值完成合并。值得注意的是上述写法中ans[-1]直接引用的是已加入的列表对象因此直接修改ans[-1][1]就能同步更新结果数组无需弹出再插入代码更简洁高效。复杂度分析时间复杂度$O(n \times \log_2 n)$其中 $n$ 为区间数量。瓶颈在于排序排序完成后的合并遍历仅需 $O(n)$。空间复杂度$O(n)$。结果数组ans最多与输入区间数量同量级全部不重叠时。为什么排序是解题的关键前提本题标签为「数组、排序」排序步骤不是可有可无的辅助而是整个算法成立的前提。AlgoNote 在 数组排序 一章中系统梳理了排序算法的分类与选择策略按时间复杂度可分为 $O(n^2)$ 的简单排序、$O(n \log n)$ 的高级排序快速、归并、堆与 $O(n)$ 的线性排序。本题采用的正是 $O(n \log n)$ 级别的排序配合 $O(n)$ 线性扫描整体达到区间合并问题的最优量级。关于排序的具体实现仓库的 快速排序源码 展示了本手册中排序算法的工程化写法通过哨兵划分partition将数组以基准数为界分成左右两部分再递归对子数组排序。本题解法中使用 Python 内置的list.sort()基于 Timsort稳定、原地即可满足需求你也可自行替换为手册中的任意排序实现来加深理解。边界情况与易错点分析单个区间intervals [[1,2]]时首个区间直接加入ans循环结束返回[[1,2]]无需特殊处理。首尾相接视为重叠[[1,4],[4,5]]中ans[-1][1] interval[0] 4不满足ans[-1][1] interval[0]走合并分支得到[1,5]。判断条件必须使用严格小于而不是这正是示例 2 考察的细节。完全包含关系[[1,10],[2,3]]中[2,3]被[1,10]完全包含合并后右端点取max(10, 3) 10区间不变结果正确。连续多段重叠[[1,3],[2,6],[8,10],[15,18]]中[1,3]与[2,6]合并为[1,6][8,10]因6 8不重叠直接加入[15,18]同理得到[[1,6],[8,10],[15,18]]。坐标非负题目约束 $0 \le starti \le endi$因此可用ans[-1][1] interval[0]这一简洁比较若坐标可能出现负数逻辑依然成立无需改动。同类题延伸区间问题的三步曲「排序 线性扫描」是区间类问题Interval Problems的通用骨架。AlgoNote 题解库中与之直接相关的题目还有0057. 插入区间输入区间本身已按左端点有序给定newInterval插入并合并。其解法将遍历分为三个阶段左侧完全不相交的区间直接加入、与新区间重叠的部分就地合并min/max扩展端点、右侧完全不相交的区间追加时间复杂度为 $O(n)$。可视为「合并区间」在已排序输入上的单次插入变体0435. 无重叠区间要求移除最少的区间使剩余区间互不重叠。其贪心策略改为按右端点排序每次选择结束最早的区间用end_pos intervals[i][0]判断是否新增不重叠区间最终答案为len(intervals) - count。与本题「按左端点排序 合并」形成鲜明对照体现了同一数据结构下排序依据的选择对解法的决定性影响。可见区间问题通常遵循三步曲确定排序依据左端点或右端点→ 线性扫描 → 按重叠条件合并或取舍。掌握了 0056. 合并区间 的基础模板再遇到同类题目时就能快速套用。总结本题在 AlgoNote 手册中被收录于「数组排序算法题目」分类见 分类刷题列表是数组 排序结合考查的代表题。其核心结论可归纳为按左端点排序后重叠判断退化为相邻区间的比较单次 $O(n)$ 扫描即可完成合并合并时右端点取max保证「恰好覆盖输入中的所有区间」整体时间复杂度 $O(n \log n)$、空间复杂度 $O(n)$是区间合并问题的最优级解。建议动手运行示例代码验证两个示例的输出并尝试用「按右端点排序」的变体重写本题体会排序依据变化带来的行为差异这将对后续攻克区间类系列题目大有裨益。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode-Go 题解精讲56. Merge Intervals 区间合并的排序与扫描算法LeetCode Go 题解精讲56. Merge Intervals 区间合并的排序与扫描算法 导读 本文基于开源仓库 LeetCode GoGo 语言实示例工程合并区间排序与贪心算法的区间合并合并区间排序与贪心算法的区间合并 问题引入 在处理时间安排、日程管理、资源分配等实际问题时我们经常会遇到区间重叠的情况。例如 会议安排系统需要合并重叠的会示例工程教程LeetCode 56 合并区间Merge Intervals全解从排序到扫描线一次吃透区间重叠合并算法LeetCode 56 合并区间Merge Intervals全解从排序到扫描线一次吃透区间重叠合并算法 导读 合并区间Merge Intervals示例工程教程上一篇【亲测免费】 clklog构建用户画像的强大工具下一篇NiGui未来路线图即将到来的macOS支持与新特性预览创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
