区间

副标题 / 摘要 合并区间是最典型的“排序 + 线性扫描”问题：先按起点排序，再顺序合并重叠区间。本文按 ACERS 结构拆解题意、核心概念、工程迁移与多语言实现，帮助你形成可复用的区间处理模型。 预计阅读时长：12~15 分钟 标签：Hot100、区间、排序、扫描线、合并区间 SEO 关键词：Merge Intervals, 合并区间, 区间合并, 排序, 扫描线 元描述：合并区间的排序扫描解法与工程应用解析，含复杂度对比与多语言实现。 目标读者 想掌握“区间合并”基础模型的初学者 需要把算法思路迁移到工程场景的中级开发者 正在准备算法面试、希望快速建立区间类题型的求职者 背景 / 动机 区间问题在日程排班、监控窗口、日志聚合、资源分配中非常常见。 如果没有一个统一的合并策略，很容易产生重复统计、冲突判断错误或资源浪费。 因此，“把重叠区间合成最少的不重叠集合”是工程与算法都高频出现的基础能力。 A — Algorithm（题目与算法） 题目还原 给定一个区间数组 intervals，其中 intervals[i] = [starti, endi] 表示第 i 个区间。 请合并所有重叠的区间，并返回一个不重叠的区间数组，且能完整覆盖输入中的所有区间。 输入输出 名称 类型 描述 intervals int[][] 区间数组，元素为 [start, end] 返回 int[][] 合并后的不重叠区间数组 基础示例（官方） 输入 输出 [[1,3],[2,6],[8,10],[15,18]] [[1,6],[8,10],[15,18]] [[1,4],[4,5]] [[1,5]] 合并示意（示例 1） 排序后: [1,3] [2,6] [8,10] [15,18] 合并: [1,3] + [2,6] -> [1,6] 结果: [1,6] [8,10] [15,18] 思路概览 按区间起点升序排序（起点相同则按终点升序）。 线性扫描，维护当前合并区间 [cur_start, cur_end]。 如果下一个区间 next_start <= cur_end，则合并为 cur_end = max(cur_end, next_end)。 否则将当前区间放入结果，并以新起点开始下一段合并。 C — Concepts（核心思想） 核心概念 概念 含义 作用 重叠 next_start <= cur_end 判断是否需要合并 合并 cur_end = max(cur_end, next_end) 扩展当前区间 排序 按起点排序 让重叠区间相邻 方法类型 排序 + 线性扫描 + 贪心合并。 ...