LeetCode 56. 合并区间：排序 + 扫描线的区间处理通用套路

题目与「重叠」的本质

LeetCode 56：给出一组区间，合并所有重叠的区间。

输入：[[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]（[1,3] 与 [2,6] 重叠，合并为 [1,6]）

「重叠」的定义：两个区间 [a,b] 与 [c,d] 重叠 = 「一个的起点在另一个的范围内」——「无序的困境」：无序数组里判断任意两区间是否重叠要 O(n²)——「排序」把重叠变成「相邻判断」——按起点排序后，「合并的候选」只可能是「相邻的区间」——「排序把全局问题降为局部问题」——与三数之和篇的「排序让去重变相邻」同一思想——「排序」是区间问题的第一工具。

解法：排序 + 扫描维护

扫描的机制：排序后从头扫描，维护「当前合并区间」 [cur_start, cur_end]——「与下一个区间的关系」三种：下一个起点 ≤ cur_end（重叠，合并：cur_end = max(cur_end, 下一个终点)）；下一个起点 > cur_end（不重叠：当前区间定稿，开新区间）；「边界情况」：起相等、端相等、「包含关系」（[1,10] 与 [2,3]——「cur_end 取 max」覆盖包含——「只比较起点」遗漏包含——「max(end)」是正确合并的关键——**「新手错误」：合并时只取下一个的终点（漏掉包含。

def merge(intervals):
    intervals.sort(key=lambda x: x[0])     # 按起点排序
    res = []
    for interval in intervals:
        if not res or interval[0] > res[-1][1]:
            res.append(list(interval))     # 不重叠：新区间
        else:
            res[-1][1] = max(res[-1][1], interval[1])  # 重叠：扩终点
    return res

「以结果数组为锚」的写法：不显式维护 cur 变量——「res[-1]」就是当前区间——「结果集的最后一个」与「扫描中的当前」合二为一——代码更短——「锚定 res[-1]」的写法在区间题中通用**。

「判断重叠」的两种写法：写法一：interval[0] <= res[-1][1]（「起点 ≤ 前一个终点」= 重叠——正向判断）；写法二：interval[0] > res[-1][1] 时新区间（「起点 > 前一个终点」= 分离——反向判断——「边界相等算重叠」（[1,3] 与 [3,5]——端点相接——题目定义下合并——「相接是否合并」要看题意（会议室 I 的重叠判定——「端点相接」在「占用」语义下是重叠——「题意的端点」要审题确认。

graph TD
    A[按起点排序] --> B{res 空 或 起点分离?}
    B -->|是| C[res.append 新区间]
    B -->|否| D[res[-1][1] = max(两个终点)]
    C & D --> E[继续扫描]

「区间问题」的通用套路

套路一：排序键的选择。按起点排序（合并、插入——「起点排序」的标准）；「按终点排序」的场景（「区间调度」——不重叠区间最多选几个——「按终点排序+贪心」——「最早结束的先选」给后面留最多空间——「排序键的选择」由「问题的目标」决定（合并看起点、调度看终点——「同一批区间、不同问题、不同排序键」。套路二：扫描的「当前区间」状态。扫描维护一个状态（「当前区间」/「当前覆盖数」——「状态」的设计决定解法——「会议室 II」（最多同时多少会议——「扫描线」：起点+1、终点-1——「事件点」的排序（「起终点的顺序」（同点先减后加——「扫描线」是区间问题的通用高级武器——把「区间」拆成「事件点」——「事件点」的排序与扫描。

「插入区间」（LeetCode 57）：已排序的区间列表 + 新区间，插入并合并——「三分段」：新区间之前（直接复制）· 重叠段（合并：start=min、end=max）· 新区间之后（直接复制——「重叠段」的循环条件（new[0] <= intervals[i][1] and new[1] >= intervals[i][0]——「重叠」的双向判断——「合并的起点」（与第一个重叠区间的起点取 min——「插入区间」是「合并」的单次版——「代码的复用」：合并区间写成通用函数——「区间函数库」的积累。「区间列表的交集」（LeetCode 986——两组区间的交集——「双指针」的区间交集（两组各自指针——交集的起 max、终 min——「起 ≤ 终」才有交集——「交集的推进」（终点小的指针前进——「双指针的区间版」——与合并两个有序数组篇的双指针同族——「区间双指针」**是区间与双指针两个家族的交汇。

长连接网关高频问答

收尾前回答两个高频问题。「接入层怎么做到轻量？」——接入层只做三件事：「接入层的极简」：连接管理（建连、心跳、断开）、消息转发（二进制协议）、不做业务解析——「鉴权的位置」（鉴权在逻辑层——接入层验 token 一次——「接入层的协议」（私有协议 vs 标准 WebSocket——「接入层的稳定」是连接不抖的前提。「连接注册表的 Redis 会不会成为瓶颈？」——注册表的架构：「注册的写量」（百万连接的心跳刷新——「注册表的优化」（本地缓存+Redis——「注册的延迟容忍」（推送失败重试的兜底——「最终一致即可」——「注册的过期」（TTL 自动清理。网关的问答收束：长连接网关的三个心智模型——「接入层是前台接线员（只管接通）、注册表是前台电话簿（找人在哪）、逻辑层是后方办公室（干活的）」——百万连接的架构，就是把「接线」与「干活」分得足够开、把「找人」做得足够快。

合并区间的高频问答与「扫描线的进阶」

合并区间的高频问答与扫描线技术的进阶应用。「合并区间的高频问答」：「端点相接算不算重叠？」——「[1,3] 与 [3,5]」——3 是左的终点也是右的起点——「取决于语义」——「连续区间」（时间段的连续覆盖——合并——「离散区间」（会议的占用——重叠——「语义决定端点」——「本题的语义」（LeetCode 56 默认合并——「会议室 I（252）」（端点相接=不重叠（3 结束后 3 开始——「252 vs 56」的端点差异——「同一批区间」在不同题目中的端点语义不同——「审题」的重要性——「端点语义」的判断——「审题一分钟」。「不排序能不能做？」——「不排序的代价」：O(n²) 的两两比较——「排序 O(n log n)」的收益——「排序是必要的」——「除非区间已经有序」——「输入的有序性」——「利用输入的有序」。「扫描线的进阶」：「扫描线的通用框架」：「事件点」的构造（起点事件+终点事件——「事件的结构」（位置+类型（起/终——「排序的事件」——「同位置的排序规则」（终点先于起点——「同点先终后起」——「扫描的状态」：当前活跃数——「活跃数的变化」——「扫描线解决的问题族」：会议室 II（最多同时）、「天际线问题（218）」——「天际线」（建筑轮廓的合并——「高度的变化」——「天际线的堆」（最大高度的维护——「扫描线+堆」的组合——「天际线」是扫描线的 Hard 应用——「扫描线」的适用性：「涉及『区间上的某个量随位置变化』的问题」——会议室、天际线、矩形面积——「扫描线」是几何/区间问题的通用武器。合并区间的高频问答总结：端点语义的审题（连续 vs 离散）+扫描线的进阶（会议室 II、天际线、事件点框架）——「合并区间」是「区间问题家族」的入门——「入门之后」：会议室（判断/计数）、插入区间、区间交集、天际线——「家族的递进」——「每一步」引入新工具（扫描线+堆）——「区间+排序+扫描」的三件套是区间问题的通用解法框架——**「掌握了框架」就掌握了整个家族。

区间合并的工程现场：日历忙闲、告警聚合与 IP 段

把视角从题面挪到生产环境，「合并区间」的三步（排序、扫描、维护当前状态）在工程里每天都被执行。「日历系统的忙闲合并」：日历服务的 free/busy 接口返回「这个人什么时候有空」——后台拿到的是一堆零散的日程块（会议 A 9:00-9:30、会议 B 9:15-10:00、全天事件……），输出前必须合并成干净的忙碌段——实现就是本题：先把所有时段按起点排序，跨天与跨时区的日程先归一到 UTC 时间戳再排（「先归一化、再排序」是区间工程的第一纪律，乱序的时区会让扫描产生假重叠）；端点语义用「左闭右开」：9:00-10:00 的会议与 10:00-11:00 的会议不冲突，[start, end) 的表示法天然消除了「相接算不算重叠」的歧义——56 题里让你纠结半天的端点问题，工程上用「约定表示法」一步绕开。「监控告警的窗口聚合」：告警平台不会给每个波动都发一条通知——同一指标的连续异常被压进一个告警窗口，恢复事件与触发事件在时间轴上同样是一堆区间，聚合器按起点排序后合并，才得到「这次故障从几点持续到几点」的结论；告警风暴时这个合并还是降噪的核心（同源告警在窗口内合并成一条）。「IP 段与路由的合并」：安全组规则、黑白名单、路由表聚合，本质都是把成千上万条 CIDR 段合并成最简覆盖——把 IP 转成整数后，每条段就是一对起止数字，扫描合并的代码与本题一字不差；max(end) 防包含遗漏的细节在这里同样生死攸关：一条 /8 的大段后面跟十条 /24 的小段，漏了取 max 就会输出一堆冗余规则。三处工程的共同结论：区间数据的通用预处理就是「归一化 → 排序 → 扫描合并」，合并完的数据才是「干净的可计算形态」——后续的交集判断、覆盖查询、可视化渲染都建立在合并结果之上。这也是为什么这道题值得写到肌肉记忆：它不是「面试题」，是区间数据的默认清洗工序。

小结

合并区间的完整解析：排序的力量（按起点排序——重叠变相邻判断——「全局问题降为局部问题」）；扫描的机制（维护当前区间——三种关系（重叠合并取 max 终点、分离开新区间）——「max(end)」防包含遗漏）；通用套路（排序键由目标决定（合并看起点、调度看终点）、扫描线的事件点、插入区间与区间交集的变体——「区间问题」是一个可以系统化掌握的家族）。给学习者的提醒：区间题的代码不长（十行内），但「边界与端点」的语义必须审题确认——端点相接算不算重叠、区间是否闭、起点是否相等——「这些语义」决定 if 的写法——「审题一分钟、省掉 WA 二十分钟」——以及，「区间问题的工程影子」：日历的忙闲合并、监控告警的时间段聚合、IP 段的合并——「区间」是后端工程师真实日常的数据形态——这道题的套路是真实工程的工具。

区间问题的解法公式：先排序，再扫描，维护一个「当前状态」——这三步组合，能解决合并、插入、交集、调度——「排序+扫描」是区间世界的万能钥匙。