LeetCode 56 合并区间：贪心思想与边界细节全解析-北京尧图网络

刚看到这题时我还以为就是个“排个序然后从头扫到尾”的轻松题结果第一次提交就被边界条件教做人了。LeetCode hot100里的第56题“合并区间”在区间类问题中属于那种“看着简单、细节暗藏”的典型代表。很多人在面试里栽跟头不是因为思路想不到而是因为判断重叠的条件和端点处理没想透。这篇就把它彻底拆开揉碎从思路推导到代码实现再到面试追问一条龙讲清楚。这题的适用人群其实很广准备算法面试的应届生、工作多年偶尔跳槽复习的老手、还有学数组/区间处理的新人都值得精练一遍。特别适合作为区间类题型的突破口——学会它后面的插入区间、会议室、区间交集都能顺藤摸瓜。1. 题目解构与核心思路1.1 题目到底在考什么先回顾一下原题给一个区间集合[[1,3],[2,6],[8,10],[15,18]]把有重叠的区间合并输出[[1,6],[8,10],[15,18]]。重叠定义很宽两个区间只要有公共部分就算重叠包括一个区间完全包含另一个区间甚至端点相接也算重叠。这道题在Hot 100里的位置很有代表性它位于数组/区间这个大类下表面看只是遍历判断实际上考察了三个底层能力一是能否识别这个问题适合排序二是能否把“两两比较是否合并”抽象成“维护一个当前合并段”三是对边界条件的敏感度——等号要不要取、空输入怎么办、能拼接的端点算不算重叠。另一个容易被忽略的点是它考察的是贪心思想在区间问题里的落地。区间类题目的战场其实就是“排序之后的一趟扫描”很多题会议室、无重叠区间、用最少数量的箭引爆气球都是这个套路的变种所以这道题学扎实了相当于是往一个可复用的解题框架里投的第一笔资金。1.2 为什么第一步必须是排序有人会想能不能不排序直接两两合并比如[[1,4],[0,2]]肉眼一看能合并成[0,4]但不排序直接处理遍历到[0,2]时它的起点 0 比前面[1,4]的起点小这时你要判断的就不是“当前区间能不能接上当前合并段”而是“当前区间能不能插到前面去”这就要回头修改已经处理过的结果代码复杂度直接翻倍。排序的真正作用是把一个依赖全局顺序的问题化简成局部顺序问题。按左端点排完序后续遍历时左端点永远单调不减那么“是否重叠”的判断就只剩一个方向只看下一个区间的左端点有没有超过当前合并段的右端点。这正好匹配贪心策略的适用条件——局部最优能推出全局最优。这里还要注意一个排序细节用lambda x:x[0]只排左端点就够了不用写双关键字排序。因为当左端点相同时谁前谁后不影响最终合并结果你不会因为它排在前面的右端点更大就丢失信息合并阶段会用max取右端点。当然写了(x[0],x[1])也不会错只是没必要。1.3 贪心策略的核心逻辑排序完成之后整个算法就可以浓缩成一段话维护一个“当前合并段”用一个结果数组来存。遍历每个区间时如果当前合并段还不存在或者当前区间的左端点大于当前合并段的右端点说明接不上就把当前合并段收尾然后开启一个新段。否则说明它们有交集只需要把当前合并段的右端点更新为两者右端点的较大值。这个逻辑的核心认知是你永远不需要回头和前面所有区间逐一比较。因为已经排序后面的区间左端点不会比前面小所以只要它跟“当前合并段”的右端点比较就够了。其实就是把问题化成一条链上的连续接龙某一段区间只要能延长就往右伸一旦断了就再也续不上前面那些区间了。2. 核心细节解析重叠判断的关键指标2.1 两个区间的六种位置关系两个区间在坐标轴上的位置关系有六种情况A 在 B 左侧且不相交、A 在 B 右侧且不相交、A 左端落在 B 内部、B 左端落在 A 内部、A 完全包含 B、B 完全包含 A。在已排序的语境下我们只需要关心下一个区间与当前合并段的位置关系能相处的情况收敛为两种一种是完全在右边不相交另一种是左端点落在当前段内部含等于右端点的情况。这就是为什么实现时只需要一个if就可以分辨当前区间的左端点大于当前合并段的右端点就是不相交否则就是相交或包含此时需要取两个右端点的最大值来扩展。如果你看到有人用“当前区间的右端点大于等于下一个区间的左端点”来判断重叠那是从另一个角度理解本质上等价但实际写代码时拿“下一个区间的左端点”和“当前合并段的右端点”比较是更顺的思路。2.2 比较对象必须是合并后的右端点这是这道题最容易写错的地方也是面试官最爱盯着看的细节。很多新手写的判断是“当前区间左端点大于上一个区间的右端点”这就是错的。原因在于经过多轮合并当前合并段的右端点可能已经被扩展得远超上一个原始区间的右端点。举一个具体的例子[[1,3],[2,6],[5,7]]。扫到[5,7]时当前合并段是[1,6]它的右端点 6 是前两个区间合并后的结果。如果你拿上一个原始区间[2,6]的右端点 6 去比5 6结果恰好也是合并没暴露问题。但如果换成[[1,4],[2,3],[4,6]]扫到[4,6]时当前合并段是[1,4]因为[2,3]被吞进去了可“上一个原始区间”是[2,3]它的右端点是 3。如果你拿 3 去比较4 3不成立就会错误地新开一段得到[[1,4],[4,6]]但正确答案是[[1,6]]。所以正确做法是维护一个独立变量或者直接取结果数组中最后一个合并段的右端点。这也是为什么建议把“当前合并段”单独存下来而不是每次去翻原始数组。这个小细节在面试里非常好用讲出来就是加分项。2.3 端点相接到底算不算重叠leetcode的原始定义里[1,4]和[4,5]是要合并成[1,5]的。也就是说闭合区间的端点相接算重叠。代码里对应的是还是的问题如果当前区间的左端点当前合并段右端点就合并反之则断开。这里有一个很常见的业务类比会议时间是闭区间上午10点到11点开会下一个会议11点到12点开始这个衔接不算冲突但在“合并区间”的语境里正好要合并成一个长日程。所以不要小看这个等号它直接决定代码正确性。如果面试官改口说“端点相接不算重叠”你只需要把这个判断从改成其他逻辑完全不变。这种改造能力也是面试官喜欢试探的点说明你真正理解了判断条件的含义而不是背代码。2.4 空输入与单区间边界边界条件虽然看起来简单但很少有人一上来就考虑全。输入是空数组怎么办输入只有一个区间怎么办更隐蔽的是输入包含多个完全相同的区间怎么办处理技巧很统一在遍历循环里用“结果数组是否为空”作为开启新段的判断条件这样不需要在函数开头单独写if not intervals: return []也能天然兼容单区间和重复区间的情况。当结果数组为空时当前区间直接作为第一段放进去之后即使遇到重复区间也只是把重复值吸收进已有段完全兼容。这个写法还有一个额外的好处它把特殊情况的处理逻辑统一成了一般逻辑代码里少一个分支review 的人看着也会顺眼很多。3. 实操过程与完整实现3.1 从思路到代码的翻译过程先把思路写成接近自然语言的伪代码再翻译成任何一门语言都会很顺畅对 intervals 按区间起点升序排序 res 空列表 for 每一个区间 interval: 如果 res 为空或 interval 的起点 res 最后一个区间的终点: res 追加 interval 的一份拷贝否则 res 最后一个区间的终点 max(res 最后一个区间的终点, interval 的终点) 返回 res这段伪代码其实已经可以直接作为面试白板答案了。它的关键位置有三处排序、空判断、max 更新。我自己在写题的时候习惯把res[-1]抽出来作为last变量这样能减少多次索引取值的书写成本也让逻辑更清楚。尤其在循环体里多次访问res[-1]时抽取变量后代码可读性会好很多。3.2 Python 实现与逐行说明def merge(intervals): if not intervals: return [] intervals.sort(keylambda x: x[0]) res [] for interval in intervals: if not res or res[-1][1] interval[0]: res.append(interval[:]) # 拷贝一份避免后续意外修改 else: res[-1][1] max(res[-1][1], interval[1]) return res逐行补充几个细节。intervals.sort(keylambda x: x[0])是 Python 里的原地排序不会产生新列表省内存res[-1][1] interval[0]用的是严格小于号说明“新段的左起点必须严格大于上一段终点”才会断开端点相等时比如4和4会被合并符合题意。res.append(interval[:])这一步拷贝的作用是后续对res[-1][1]的修改不会反向污染原始输入数据。如果面试官问“为什么拷贝”你可以回答数据是不可变快照避免副作用对于不可变元组构成的输入这一步也可以写成list(interval)。3.3 Java 与 C 实现的对照public int[][] merge(int[][] intervals) { if (intervals.length 0) return new int[0][]; Arrays.sort(intervals, (a, b) - a[0] - b[0]); Listint[] res new ArrayList(); for (int[] interval : intervals) { if (res.isEmpty() || res.get(res.size()-1)[1] interval[0]) { res.add(new int[]{interval[0], interval[1]}); } else { res.get(res.size()-1)[1] Math.max(res.get(res.size()-1)[1], interval[1]); } } return res.toArray(new int[res.size()][]); }vectorvectorint merge(vectorvectorint intervals) { if (intervals.empty()) return {}; sort(intervals.begin(), intervals.end()); vectorvectorint res; for (auto interval : intervals) { if (res.empty() || res.back()[1] interval[0]) { res.push_back(interval); } else { res.back()[1] max(res.back()[1], interval[1]); } } return res; }两个版本在语言细节上稍微有点差异。C 里sort(intervals.begin(), intervals.end())可以直接对二维vector排序因为vectorint默认按字典序比较左端点相同的时候会再比右端点排序结果依然正确。Java 的 lambda 写法(a,b)-a[0]-b[0]在 a[0] 极大时可能溢出面试时提一嘴改成Integer.compare(a[0], b[0])会更稳属于展示代码素养的细节。3.4 复杂度分析时间复杂度是O(n log n)瓶颈在排序。后面的线性遍历是O(n)所以整体就是排序的复杂度。空间复杂度分两块结果数组如果算输出空间那就是O(n)如果只算额外辅助空间在 Python 的 sort 和大多数语言的基础排序实现里栈空间是O(log n)所以额外空间可认为是O(log n)。面试时可以把复杂度顺口说出来排序阶段 O(n log n)、扫描阶段 O(n)、结果空间 O(n)。如果有人追问“能不能优化到 O(n)”标准回答是如果输入保证是有序的那就能做到 O(n) 时间否则比较排序下界就是 O(n log n)但可以用特殊的非比较排序场景比如区间端点范围很小的时候用桶排不过面试通常不会要求到这层深度。4. 常见问题与排查技巧实录4.1 最常见的错误忘了排序我没见过任何一个写过这道题的人能完全避开这个坑。忘排序的典型症状是给定乱序输入比如[[2,6],[1,3],[8,10],[15,18]]代码会输出[[2,6],[1,3],[8,10],[15,18]]或者错误合并总之与正确答案不符。这种错误的隐蔽性高因为有些乱序输入恰好能跑出正确结果容易让错误思路“侥幸过关”。排查技巧很简单写题时准备一组“故意乱序包含关系”的测试用例比如[[2,6],[1,3],[0,10]]。如果代码没排序这种用例几乎必然出错。习惯上我在写完合并区间代码后第一件事就是人为打乱输入顺序再跑一次看是否跟排好序的输入结果一致。这种自检习惯能挡掉相当大一类排序依赖型题目的低级错误。4.2 比较对象拿错用了原始区间的右端点对齐一下错误代码长什么样for i in range(1, len(intervals)): if intervals[i][0] intervals[i-1][1]: # 合并...这个写法看似有道理但它只在intervals[i-1]恰好还没被合并时才正确。一旦前面的区间被合并过intervals[i-1][1]就不再代表当前合并段的右边界。前面 2.2 节已经举例了这里不重复但要强调的是这是纯逻辑层面的错误不靠调试很难发现因为边界用例不够多时很容易被“刚好正确”的结果掩盖。我的排查办法是写一个简单工具函数把结果用断言与前一次输出的结果比对专门对“能连续多段合并”的数据做压力测试。比如[[1,2],[2,3],[3,4],[4,5]]这种每一段都能接上的链条答案应该是[[1,5]]。很多错误实现面对长链条时会输出多个相邻但不该断开的区间非常直观。4.3 原地修改列表导致的怪异问题有些解法想少用空间直接在原数组上做标记、删减或覆盖结果容易出现两个问题一是遍历过程中修改列表长度会跳过元素二是信号源被污染后续依赖原数据的逻辑全乱套。最稳的做法就是新建结果数组。如果你担心append(interval[:])拷贝开销可以明确跟面试官说这里是引用语义原数组元素不会改动所以不需要拷贝。实际上如果确定后续只会读取interval[0]和interval[1]并且不会修改原数组直接 append 原区间也不会出错。但为了防御未来改动拷贝更安全。面试时我会直接 append 原对象然后解释一句“因为我没有修改原数组的区间值只是读取所以不需要深拷贝”也能体现对引用/值语义的理解。4.4 “用右端点排序能不能做”面试里我遇到过几次追问“为什么按左端点排序按右端点排序行不行”答案是能但处理逻辑会变复杂。按右端点排序后合并的语义变成了“向前看”你得从后往前合并而且因为右端点有序左端点是混乱的需要记录已合并段的最小左端点从逻辑上不如按左端点排序顺。如果面试官就是故意让你按右端点排序你可以在白板上写一版对比展示这里多出的min更新。这个对比很加分说明你理解排序方向会影响遍历逻辑和状态维护方式。4.5 与相邻题的辨析为什么会议室那题更简单有一个高频混淆点会议室问题判断能否参加所有会议看起来和合并区间很像但解法却不需要维护合并段。会议室问题只需要判断是否存在重叠做法是排完序后遍历检查每一个区间是否与上一个区间重叠一旦重叠就返回 false。它不需要“合并”因为只要有一个重叠就无法参会。合并区间和会议室问题的本质差异在于一个关心连续段的累积前缀一个关心相邻两者的局部冲突。很多初学者把这两题弄混用一个带 max 更新的循环写会议室虽然结果也是对的但代码里充斥着没必要的状态维护反而降低了可读性。反过来拿会议室题的“只和上一个比”逻辑去写合并区间就会踩到 4.2 的坑。把这两题的差异在脑子里对比清楚你的区间题框架才算真正建立起来。5. 同类问题对比与扩展5.1 插入区间合并思想的分段应用插入区间是很自然的延伸题给一组已经排序且合并好的区间再插入一个新区间返回合并后的结果。很多解法是拿新区间跟原始区间逐个合并但更清晰优雅的思路是拆成三段——左侧完全不重叠的区间直接进结果中间与新区间有重叠的部分用一个累计合并段处理右侧剩余区间再直接进结果。这个“三段式”其实就是合并区间里“找到重叠窗口合并窗口内容”的思想只是多了个窗口定位步骤。学完合并区间后再看插入区间就会有一种“So Easy”的感觉因为它不再需要排序拿排序的框架省一轮复杂度直接变成 O(n) 遍历。反过来如果不理解合并区间的max更新逻辑写插入区间时很容易在窗口边界判断上出错。5.2 区间类题型的共性与差异合并区间、会议室、无重叠区间、用最少数量的箭引爆气球、划分字母区间这些题的共同点是都基于排序后的一次扫描但扫描时维护的状态完全不同。用最少数量的箭引爆气球要维护的是一条箭的右端点尽可能小因为这决定你能覆盖多少后续气球无重叠区间要求移除尽可能少的区间使剩余区间不重叠用的是贪心选最早结束的思路划分字母区间则是扫描并维护当前片段的最大右端点。它们的差异表面上是状态变量的含义不同底层其实是“目标函数”不同。把这几题放在一起做对比整理是最快的题感训练方式。5.3 区间合并的工程应用从算法题到生产场景这道题的场景价值完全不只在面试。就拿日程管理系统来说用户一天可能创建多个跨时段的日程为了在视图中展示“忙碌时间段”第一件事就是把重叠的日程合并成大块时间段合并区间算法直接上场。日志系统里也有类似场景分布式请求会产生起始时间和结束时间有重叠的多个 span为了按链路聚合耗时需要把重叠时间片段合并数据库里的范围查询、订阅系统的价格区间过滤、甚至视频剪辑软件的时间轴片段合并本质上都是同一个逻辑。所以面试官爱考这道题不只因为它经典更因为它能快速判断一个人是否具备“把现实问题抽象成区间模型”的意识。你可以把这句经验放在项目介绍的“技术亮点”里比空泛地说“我用过排序算法”有说服力得多。5.4 变体扩展区间交集与区间差集沿同一个方向再扩展一步如果给两个已经分别合并好的区间列表要求输出两者的交集该怎么做思路是双指针两个指针分别指向两个列表的当前区间取max(左端点)作为交集左边界、min(右端点)作为交集右边界如果左右就输出然后移动右端点较小的那一边的指针。区间差集同理要维护更多状态。这些变体虽然不常考但在高阶面试里出现过。我的建议是先吃透合并区间再花一个下午把交集、差集、对称差集的伪代码各写一遍它们之间是状态的组合叠加逻辑基础还是那一个排序扫描框架。写在最后的实践经验我自己第一次写这道题用了大概 20 行代码其中 6 行都是在处理“当前合并段的右端点到底是谁”这个问题。现在回看我觉得吃透这道题的关键就是回答三个问题排序解决的是什么、比较对象为什么要动态维护、等号到底算不算合并。把这三句话能用自己的话讲清楚面试官一般就不会再追问更多。最后分享一个小技巧刷区间类题目的时候我习惯在草稿纸上画数轴把区间标注成线段然后手动跑一遍算法。这个简单的可视化动作能帮你快速定位比较对象写错、边界条件写反这类问题比在 IDE 里打断点调试快得多。合并区间这道题能在 Hot 100 里站住脚不是因为它难而是因为它浓缩了区间题型的全部核心思想值得反复咀嚼几遍。

LeetCode 56 合并区间：贪心思想与边界细节全解析

相关推荐

城市计算技术框架全拆解：从感知层到服务编排的工程落地实践

Git本地文件夹同步三步法：初始化、提交、关联远程

leetcode面试经典150刷题实录：二分查找与二分答案详解

更多资讯

Spring生态修炼指南：从IoC/AOP到微服务与AI集成

神经元真相：从数学压缩器到工业级训练的硬核工程实践

JDK17升级全解析：从新特性到迁移避坑指南

文件摆渡系统选型实战：从需求梳理到测评避坑全指南

klogg 实战：2GB 日志秒开与搜索优化指南

DBSCAN场景削减MATLAB实现：风电-负荷随机优化高效聚类方法

今日更新

再见，SSE！你好，Streamable HTTP！轻松开发 Streamable HTTP MCP Server 并接入 TaoToken

工业软件标准化路线图：国产替代的落地施工图

VCMI安卓版实操指南：原生运行英雄无敌3的3步技术落地

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？