合并区间最优解：排序加线性扫描，LeetCode56题详解-北京尧图网络

先把结论放在前头合并区间LeetCode 56 题最稳的解法就是排序加线性扫描。输入给的区间顺序是完全随意的不排序你怎么看都别扭。只要按左端点从小到大排好一条一条过能合并就合并、不能合并就新开一段代码控制在十行左右。很多人第一次做这题会去暴力两两比较结果越合越乱最后要么超时要么漏情况。这篇文章我分五个部分讲透题目怎么拆、重叠判断怎么写、代码怎么落地、同类型题怎么迁移最后再给一份自查清单直接照着用。适合谁看刚刷完链表、二叉树、递归这些基础题正往“排序类题目”过渡的新手或者准备面试但总在边界条件上栽跟头的老手。这题属于“看着简单、写全对不容易”的典型考点并不在于某个炫酷的数据结构而是你能不能处理干净数组、排序、指针这类最基础的细节以及在面试官追问变体时快速迁移。1. 题目解析与思路拆解1.1 先把题“翻译”成人话力扣给出的输入是若干区间每个区间一对[start, end]表示数轴上的一段范围。目标是把所有重叠的区间全部合并返回合并后的新区间列表。比如输入[[1,3],[2,6],[8,10],[15,18]]因为我们有[1,3]和[2,6]在数轴上有重叠合并成[1,6][8,10]与[15,18]中间隔了空隙不能合。所以输出[[1,6],[8,10],[15,18]]。题目里还有一条容易被忽略的规则区间首尾相接也算重叠。比如[1,4]和[4,5]4 这个点是共用的它们应该合并成[1,5]。这一点很关键很多人第一次做会在这里写错成cur[0] last[1]少了一个等号。从数据结构上看这题没有任何高难度操作不涉及树、图、动态规划就是数组遍历。可它偏偏是热门前 100 题深挖原因只有一个它把排序思维、边界讨论和代码实现压在一起考察。1.2 不排序为什么容易把自己绕进去假设输入是乱序的[[2,6],[1,3],[8,10],[15,18]]。如果不排序你会发现[2,6]和[1,3]重叠了于是你把它俩合并成[1,6]。合并出来的[1,6]还可能跟另外某个区间重叠于是你又要回头继续检查。合并结果本身会改变后续判断这是一种“连锁反应”全靠肉眼和两两比较很难穷尽。如果非要用“两两比较反复合并”的思路最坏情况下需要多次遍历复杂度会退化到接近O(n^2)而且代码里要维护“哪些区间已经被吸收掉了”的状态极易出错。排序解决的第一件事就是把这种不可控的连锁反应变成“单向推进”。你一旦按左端点升序排序从左往右扫每个新区间只需要关心“它有没有和当前结果里最后一段重叠”。因为后面区间的左端点只会一个比一个大一旦某个区间没办法和当前合并段重叠那么它也不可能和结果里更靠前的区间重叠——更靠前的区间终点只会更小。这是整个算法成立的核心逻辑。1.3 为什么“只看最后一段”就够了很多初学者卡在这里为什么合并时不需要反复和结果里的每一段比较我们维护的“当前合并结果最后一段”其实就是从扫描起点开始一直到现在所有和它能连续覆盖的区间合并出来的最大覆盖段。排序保证了任何新区间的左端点一定不小于前面所有区间的左端点。所以只需判断这个新区间的左端点是否落在最后一段的右端点之内。用生活场景类比你在安排会议时间。所有会议按开始时间排序你记下当前最后一段被占用的时间范围。如果下个会议开始时间还不晚于当前占用的结束时间那就说明它们可以连成一片延长占用时段即可。如果下个会议已经开始于当前空闲之后那之前这一段彻底结束以后的时间段也不可能再“回填”到前面去。这种贪心策略之所以正确核心在于区间排序后的单调性左端点递增让判断条件从“多重比较”简化成了“一个条件”。2. 核心细节解析与关键判定2.1 重叠判定只有一条公式假设last [a, b]是已合并区间的最后一段cur [c, d]是当前区间。由于我们按左端点排序必然有a c。那么重叠的判定条件就是c b只要当前区间的开头不晚于已合并区间的结尾两个区间就有交集需要合并。但合并时有一个很多新手会踩的大坑新区间的右端点不一定等于d而是max(b, d)。举个例子last [1, 5]cur [2, 3]。两个区间重叠可是如果把右端点更新成cur[1]那么[1, 5]会退化成[1, 3]把后面的范围丢了。正确做法是保留两者右端点的较大值得到[1, 5]。这算这类题的核心公式if c b: b max(b, d) else: 开启新的一段一个只覆盖半段、被完整包裹的情况就是测试你公式写完没有的典型用例。答案是只要写对max完全包裹也天然被正确处理。2.2 排序按左端点不要按右端点排序键的选择不用纠结必须按左端点升序。反过来的话整个“只看最后一段”的贪心推理会失效。你可以简单验证一下如果按右端点升序排列一个超大区间可能出现在中间位置比如[1, 100]排到后面它会把前面所有小区间都覆盖掉但扫描时前面的区间可能已经各自成段最后还是得回头合并逻辑就乱了。按左端点排序才能保证单调地向右推进。排序时还有个隐藏问题如果两个区间左端点相同怎么处理比如[1, 4]和[1, 2]。此时谁在前谁在后都能得到正确结果因为我们在合并时用max取右端点。但为了让自己推导方便保持升序即可。Python 直接写intervals.sort(keylambda x: x[0])Java 则建议这样写Arrays.sort(intervals, (a, b) - Integer.compare(a[0], b[0]));这里有个非常实际的小坑不少人图省事会用a[0] - b[0]作为比较器。当两个左端点悬殊很大时int减法可能溢出产生意料之外的排序结果。面试时最好写成Integer.compare既安全也显得你懂边界。2.3 动手之前先把边界情况在脑子里过一遍这类题最容易翻车的不是主线逻辑而是各种“特判”。我建议你拿到题先想清楚下面这些用例输入为空数组时返回空数组就好输入只有一个区间时无论如何都只有一个答案所有区间都重叠时比如[[1,5],[2,4],[3,6]]答案应该是一整段两个区间完全不相邻比如[[1,2],[3,4]]输出保持原样两个区间首尾相接比如[[1,2],[2,3]]必须合并成[1,3]。这些事情不是“如果有时间再测”而应该成为写代码前的默认输入。面试时你把这种边界意识讲出来就已经比一半候选人强了。3. 代码实现与完整推演3.1 Python 解法逐行拆解先用最通用的写法def merge(intervals): if not intervals: return [] intervals.sort(keylambda x: x[0]) merged [intervals[0]] for current in intervals[1:]: last merged[-1] if current[0] last[1]: last[1] max(last[1], current[1]) else: merged.append(current) return merged逐行看先处理空数组避免后面访问intervals[0]直接报错。原地排序因为题目没有要求保留原输入顺序。如果你担心修改入参可以改成sorted(intervals, keylambda x: x[0])面试时提一句“我知道这题改原数组没关系但如果业务中不允许我会用副本”这是加分项。merged [intervals[0]]是初始化整个算法的前提把第一个区间当作当前合并段的起点。这里直接把引用放进去后面修改last[1]就是修改intervals[0]。由于原数组后续不再需要代码可读性更好逻辑也更简洁。循环从intervals[1:]开始逐个处理剩余区间。判断条件是current[0] last[1]注意这里有等号对应我们前面说的首尾相接。合并动作只改右端点last[1] max(last[1], current[1])。这个max是处理“完全包含”的关键。当当前区间起点大于last[1]说明它跟前面所有区间都不重叠直接新增到结果末尾然后继续向后扫。如果把“原地修改 merged[-1]”写成更显式的版本可以是merged[-1][1] max(merged[-1][1], current[1])效果一样看你喜欢哪种风格。我面试时更愿意用merged[-1]因为变量越少现场讲代码越轻松。边界条件里还有个容易被忽视的细节如果输入长度是 1循环不会执行直接返回[intervals[0]]结果正确。所以不需要为长度 1 单独写if len(intervals) 2有些人的冗余判断反而让它看起来不干净。3.2 Java 解法与几个差异点力扣原题的 Java 函数签名是int[][] merge(int[][] intervals)。参考答案如下public int[][] merge(int[][] intervals) { if (intervals.length 0) { return new int[0][]; } Arrays.sort(intervals, (a, b) - Integer.compare(a[0], b[0])); Listint[] merged new ArrayList(); merged.add(intervals[0]); for (int i 1; i intervals.length; i) { int[] current intervals[i]; int[] last merged.get(merged.size() - 1); if (current[0] last[1]) { last[1] Math.max(last[1], current[1]); } else { merged.add(current); } } return merged.toArray(new int[merged.size()][]); }这里有几个和 Python 不同的地方值得说Java 的二维数组长度固定合并后长度变化必须借助ArrayList过渡最后再toArray转回二维数组。last是int[]引用修改last[1]会同步修改merged里存的数组因为它们是同一个引用。这一点刚好方便我们做原地更新。用Integer.compare而不是减号避免整数溢出。return new int[0][];表示返回一个“空二维数组”而不是null。如果面试官说“别用额外空间原地合并”可以做到吗可以。做法是把合并结果写回 intervals 数组的前面部分用一个额外索引表示写入位置。但建议先写出常规版本再提“我可以用双指针原地压缩需要的话我一分钟改好”这样既稳定又显得有储备。3.3 拿两个典型用例完整推演一遍推演是让思路扎实最有效的办法。第一个用例是官方示例intervals [[1,3],[2,6],[8,10],[15,18]]排序后不变merged [[1,3]]遍历到[2,6]2 3所以合并merged [[1,6]]遍历到[8,10]8 6新增merged [[1,6],[8,10]]遍历到[15,18]15 10新增最终[[1,6],[8,10],[15,18]]这个用例相对平凡。再看一个能同时测出“包含”和“首尾相接”的用例[[1,4],[2,3],[3,6],[6,8]]排序后还是这个顺序。推演merged [[1,4]]当前[2,3]2 4合并由于 3 小于当前右端点 4更新后仍为[1,4]当前[3,6]3 4合并max(4,6)6更新为[1,6]当前[6,8]6 6等号成立首尾相接也算重叠合并成[1,8]最终输出[[1,8]]。这个过程我强烈建议你面试前自己手写一遍。合并区间这种题很多人代码背得滚瓜烂熟但面试官让“讲一下你的代码怎么处理 [2,3] 被 [1,4] 包含的情况”时如果没推演过容易卡壳。3.4 复杂度排序是唯一的“性能账单”这道题的时间复杂度很好算排序O(n log n)其中n是区间数量这是整个算法的瓶颈。线性扫描每个区间最多被访问一次O(n)。总复杂度O(n log n)。空间复杂度主要来自结果数组最坏情况下所有区间都不重叠要存n个区间所以为O(n)。如果题目本来允许把结果写回原数组理论上可以做到O(1)额外空间但通常不值得为了空间开销牺牲代码清晰度。回答复杂度时还有一个加分表述如果不能修改原数组且使用了额外结果数组那空间开销本来就是答案的一部分如果输入本身已经按左端点排好序那排序步骤可以省略整个算法会变成O(n)。4. 变体、进阶与同类题迁移4.1 插入区间一个几乎共享核心逻辑的变体力扣第 57 题“插入区间”输入已经按左端点排好序再给你一个新区间要求把它插进合适位置并合并重叠部分。这种题其实就是合并区间的“限定有序版本”。如果你已经把 56 题的逻辑吃透了57 题最直白的思路是把所有右端点小于新插入区间左端点的区间原样加入结果把所有左端点小于等于新区间右端点的区间逐一和新插入区间合并更新左右两端其余区间原样加入结果。核心合并条件依然是要合并的区间满足当前区间左端点新区间右端点。而新区间的边界不断用min和max扩展。代码写出来和“合并区间”很像只不过不是把新区间追加到数组末尾再整体 merge而是边扫描边处理。如果面试官允许你“懒一点”你把新区间添加进原数组重新调用 merge 函数也能得到正确答案。但这样多了一次排序白白把O(n)的解法退化成了O(n log n)在有经验的面试官面前会显得不够细致。4.2 区间交集、会议室与工程场景合并区间只是“区间类题目”家族里的基础款。和它经常一起出现的还有区间交集力扣 986两个有序区间列表求它们在数轴上的交集。思路是双指针每次取left max(l1, l2)、right min(r1, r2)若left right就记下一段交集然后让右端点较小的数组前进。它和合并区间的区别是找“公共部分”而合并区间找“并集部分”。会议室力扣 252/253给定一组会议时间判断能否全部参加或至少需要多少间会议室。核心思路之一是扫描线区间开头计1结尾计-1然后求累计最大值。这和合并区间的排序贪心高度相似。合并区间本身常常是下一问的预处理。面试官会先问你“合并区间”再追问“合并之后所有覆盖的总长度是多少”。此时你只要把合并后的每个区间长度累加即可。答得好不好取决于你合并的函数写得干净。工程里我见过最像的场景是“IP 段合并”和“服务器资源预约合并”。比如一段 Trunk 端口预留了哪些连续资源或者某系统记录了很多碎片时间需要把它们合并成整段。做题的排序与扫描思路直接搬到这些场景里也毫无违和感。5. 常见错误与排查思路5.1 五个高频翻车点我在实际写这题时踩过不少坑也帮别人 review 过很多版本总结下来最容易出的几个问题第一个把重叠判断写成current[0] last[1]把等号漏了。这会让[2,3]和[3,5]这种合法连续区间无法合并。记住首尾相接在题目里是重叠。第二个合并右端点时不取 max。如果当前区间完全被最后一段包含比如[1,6]和[2,4]直接用current[1]覆盖结果会错误地缩短成[1,4]。只要写一次max就能杜绝。第三个先排序再写循环时把排序后的数组引用搞混。比如有人为了不修改原数组额外创建了newIntervals但合并结果又拿原数组的第一个元素初始化逻辑就乱套了。初始化结果时一定拿排序后的第一个元素。第四个尝试在遍历中原地删除被合并的区间。如果一边遍历原数组一边删除元素顺序和索引都会出问题而且时间复杂度可能变成O(n^2)。老老实实把所有区间统一放进新结果列表或者用写入指针压缩。第五个Java 排序比较器用减号。我们前面提到过a[0] - b[0]在极端取值下会溢出造成排序结果完全错误。直接用Integer.compare面试官绝不会说你有问题。5.2 一份可以直接抄的自查清单写完代码不要急着提交。按下面这份清单跑一遍测试用例能覆盖绝大多数意外情况用例输入预期输出说明空数组[][]防 NPE单区间[[5,7]][[5,7]]最少代码路径全部重叠[[1,4],[2,5],[3,6]][[1,6]]连续吸收完全包含[[1,6],[2,4]][[1,6]]测 max 逻辑首尾相接[[1,2],[2,3]][[1,3]]测等号无重叠[[1,2],[3,4]][[1,2],[3,4]]不误合并乱序输入[[5,6],[1,2],[3,4]][[1,2],[3,4],[5,6]]验证排序提交之前把这张表在脑子里过一遍或者用这几个用例在本地把代码 run 一遍基本就能避开 90% 的边界坑。5.3 排查的推荐流程如果你本地跑一个用例没过不要盯着代码乱猜我的习惯是这样先拿最简用例定位失败路径例如只放两个区间判断是排序问题还是合并问题。再打印每一步的关键变量尤其是每次循环里的current[0]、last[1]、更新后的右端点。不要嫌麻烦打印输出比肉眼追代码快得多。确认逻辑问题之后回去检查三处有没有漏等号、有没有忘了 max、初始化是不是用了排序后的第一个区间。我见过的大多数错误最后都落在这三处。还有一个小技巧调试时把区间想象成数轴上的线段在纸上画一画。你很快就会发现自己哪一步把“包含”关系处理错了。画图不是低效手段反而是在区间题里最高效的方式。6. 最后说点实操心得合并区间这类题几乎不会单独考你一个“会不会背代码”的问题。面试官更想看到的是你能不能把边界条件想全。我的实操习惯是写完代码后主动在代码旁边写出三行注释第一行写排序保证什么第二行写重叠判断的条件第三行写为什么右端点要取 max。这样一方面防止自己写到一半忘逻辑另一方面也是在向面试官展示思路。另一个个人体会是这类题的描述虽然短但它背后藏的区间处理技巧几乎可以通吃一整个“区间类”题目家族。认真把这一题推演几遍再做插入区间、会议室、区间交集你会觉得大半个数组类题目的套路都打通了。最后分享一个小经验面试时如果遇到合并区间你可以主动问一句“输入有没有可能已经有序”。这不是废话而是体现了你考虑问题的习惯。如果没有排序才需要你明确写出sort如果已经有序最优解会直接从O(n log n)降成O(n)。处理好这一步面试官会认为你不只是一台“刷题机器”而是真的理解问题本身。

合并区间最优解：排序加线性扫描，LeetCode56题详解

相关推荐

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

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

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

更多资讯

模拟企业开发环境搭建五天实战：从裸机到可协作可复现环境

Python的循环里别用+=拼接字符串，真的会慢到哭

链表头结点详解：从原理到实战，彻底解决指针边界问题

PHP轻量课表查询系统：基于XMLReader的Excel解析与RESTful课表服务

别等迷路才下载：5 款户外轨迹导航 APP 实测与适配人群

Fedora 安装 Microsoft Edge 官方仓库配置与常见问题排查指南

今日更新

再见，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 成本测算与选型避坑（附配置）

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