题目描述
思路解析
一句话答案：LeetCode 56 合并区间的标准解是先按起点排序、再一趟线性扫描：维护「当前合并段」的右端 curE，新区间起点 s ≤ curE 就把右端拉成 max(curE, e) 继续并，s > curE 就把旧段封口、另起新段。排序保证每个区间只可能与最近一段重叠，整体时间 O(n log n)、空间 O(n)。
合并区间这道题在问什么
给一堆可能互相重叠的区间 [start, end]，要求把所有叠在一起的区间合并成一段，输出一组互不重叠、又恰好覆盖全部输入的区间。比如 [[1,3],[2,4],[6,8]]，前两个叠着，合成 [1,4]，答案是 [[1,4],[6,8]]。难点不在「怎么合两个区间」，而在乱序输入下怎么知道谁和谁该合——这决定了第一步必须是排序。
为什么合并区间必须先按起点排序
如果不排序，直接从左往右扫，你没法只和「上一段」比：后面随时可能冒出一个起点更小的区间，回头和早已处理过的段重叠，一趟扫描就失效了，只能退化成两两比较。
按起点从小到大排序后，起点单调不减，一个新区间要么接在最近合并出的那段上（重叠或相接），要么整体落在它右边。它绝不可能越过最近一段去和更早的段重叠——因为更早的段已经被最近一段「吞并或隔开」了。于是每个区间只需做一次比较，线性一趟就够。
怎么判断两个区间重叠，等号算不算
扫描时手里始终握着一个「当前合并段」，只关心它的右端 curE。新区间 [s, e] 来了就比一次：s ≤ curE 说明新区间的头没越过当前段的尾，两段叠着或端点相接，并进去；s > curE 说明中间断开了，旧段定型收进结果，用 [s, e] 另起一段。
等号必须算重叠：[1,3] 和 [3,5] 在 3 处相接，按题意要合成 [1,5]，判断写成 s < curE 就会把它们错误拆开。另一个细节是合并时右端要取 max(curE, e) 而不是直接赋成 e——新区间可能被当前段完全包住，比如当前段是 [1,9]、来了个 [2,5]，直接赋值会把右端从 9 改小成 5。
为什么当前段的起点永远不用更新
因为区间已按起点排序，当前段的起点是这一片区间里最小的起点；之后并进来的区间起点只会更大，不可能把段的左边界往左推。所以合并动作只有一个方向：右端往大里拉。这也解释了为什么整个算法状态可以精简到只记 res 里最后一段——参考代码里 res[-1][1] = max(res[-1][1], e) 一行就是全部合并逻辑。
复杂度怎么算，有哪些边界
时间 O(n log n)：瓶颈在排序，排好后线性扫一遍只花 O(n)。空间 O(n)：结果数组最坏放下全部 n 个区间（两两不重叠时原样输出）；反过来最好情形所有区间连成一片，结果只剩 1 个。
最容易翻车的三处：忘记排序直接扫、漏掉端点相等的重叠、合并时不取 max 导致右端被改小。写完拿一组含「完全包含」和「端点相接」的用例各验一遍，基本就稳了。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住一个判断：新区间起点 s 和当前段右端 curE 比大小。s ≤ curE 就并（拉长右端）；s > curE 就断（封旧段、开新段）。下面每一帧都在套这条规则。
排好序后，把第 1 个区间 [1,2] 设为「当前合并段」（绿色高亮）。curE = 2，从下一个区间开始往后并。
指针走到第 2 个区间 [1,3]，它的起点 s = 1。当前合并段右端 curE = 2。1 没越过 2，两段挨着或叠着。
s ≤ curE，重叠！把它并进当前段：起点仍是 1，右端拉到 max(curE, 3) = 3。当前段变成 [1,3]（绿色组多了这一格）。
指针走到第 3 个区间 [2,4]，它的起点 s = 2。当前合并段右端 curE = 3。2 没越过 3，两段挨着或叠着。
s ≤ curE，重叠！把它并进当前段：起点仍是 1，右端拉到 max(curE, 4) = 4。当前段变成 [1,4]（绿色组多了这一格）。
指针走到第 4 个区间 [3,4]，它的起点 s = 3。当前合并段右端 curE = 4。3 没越过 4，两段挨着或叠着。
s ≤ curE，重叠！把它并进当前段：起点仍是 1，右端拉到 max(curE, 4) = 4。当前段变成 [1,4]（绿色组多了这一格）。
指针走到第 5 个区间 [5,5]，它的起点 s = 5。当前合并段右端 curE = 4。5 越过了 4，中间断开了。
s > curE，断开！把旧段 [1,4] 收进结果（变灰封口），再用 [5,5] 开一个新的当前段（绿色组重置到这一格）。
指针走到第 6 个区间 [6,7]，它的起点 s = 6。当前合并段右端 curE = 5。6 越过了 5，中间断开了。
s > curE，断开！把旧段 [5,5] 收进结果（变灰封口），再用 [6,7] 开一个新的当前段（绿色组重置到这一格）。
指针走到第 7 个区间 [6,8]，它的起点 s = 6。当前合并段右端 curE = 7。6 没越过 7，两段挨着或叠着。
s ≤ curE，重叠！把它并进当前段：起点仍是 6，右端拉到 max(curE, 8) = 8。当前段变成 [6,8]（绿色组多了这一格）。
指针走到第 8 个区间 [7,8]，它的起点 s = 7。当前合并段右端 curE = 8。7 没越过 8，两段挨着或叠着。
s ≤ curE，重叠！把它并进当前段：起点仍是 6，右端拉到 max(curE, 8) = 8。当前段变成 [6,8]（绿色组多了这一格）。
指针走到第 9 个区间 [8,9]，它的起点 s = 8。当前合并段右端 curE = 8。8 没越过 8，两段挨着或叠着。
s ≤ curE，重叠！把它并进当前段：起点仍是 6，右端拉到 max(curE, 9) = 9。当前段变成 [6,9]（绿色组多了这一格）。
指针走到第 10 个区间 [9,9]，它的起点 s = 9。当前合并段右端 curE = 9。9 没越过 9，两段挨着或叠着。
s ≤ curE，重叠！把它并进当前段：起点仍是 6，右端拉到 max(curE, 9) = 9。当前段变成 [6,9]（绿色组多了这一格）。
扫到末尾，把最后的当前段也收进结果。最终合并出 [1,4] [5,5] [6,9] 这 3 段互不重叠的区间，就是答案。
留意端点相接这种边界：起点等于上一段右端，仍按重叠合并。
三个高频追问：排序的必要性、curE 的含义、结果区间数的范围。
参考代码
def merge(intervals): intervals.sort(key=lambda x: x[0]) # 按起点排序 res = [] for s, e in intervals: if res and s <= res[-1][1]: # 与上一段重叠 res[-1][1] = max(res[-1][1], e) else: # 断开，另起一段 res.append([s, e]) return res复杂度
- 时间：O(n log n)，瓶颈在排序；排好后只扫一遍 O(n)，所以总体 O(n log n)
- 空间：O(n)，结果数组最多放下 n 个区间；不算结果的话排序额外空间 O(log n)
易错点
面试追问把动画讲成自己的话
追问为什么必须先排序？
追问curE 代表什么？为什么起点不用动？
追问结果区间的总数最少 / 最多是多少？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
无重叠区间
LeetCode 435 · 中等 · 沿着 区间 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题