hot100 合并区间(56)

本题采用基于左端点排序的贪心算法解决“合并区间”问题。其核心本质是通过对区间起始边界进行单调递增排序将无序的二维几何重叠判定降维成一维线性的右边界扩展问题。该解法的时间效率上限完全取决于排序算法的开销当前状态为解决区间重叠问题的标准范式最终走向是输出一个拓扑有序且互不相交的连续覆盖区间集合。一、 问题本质与数据模型在几何学与实分析中一个闭区间可以表示为数轴上的一个集合。给定一系列区间其在数轴上的空间分布是任意的。两个区间 A [start_A, end_A] 和 B [start_B, end_B] 存在重叠的核心物理条件为两个区间的交集非空。如果在未排序的状态下寻找重叠必须对任意两个区间进行两两比对判定方程组是否满足以下交集条件max(start_A, start_B) min(end_A, end_B)为了消除这种非线性的高额检索开销算法引入了全序排序Total Ordering。通过将所有区间按照左端点起始位置进行单调递增排序建立了空间的单调性。在排序后的区间序列中如果存在前后两个相邻区间last和cur由于已经满足last[0] cur[0]因此它们发生重叠的充要条件被极大简化为cur[0] last[1]也就是说只要后一个区间的起点不大于前一个区间的终点两者在几何空间上就必然存在重叠。二、 算法演进对比在处理区间拓扑合并问题时排序加贪心扫描的方案在执行效率上表现最优解法名称时间复杂度空间复杂度核心原理物理瓶颈图连通分量法O(n^2)O(n^2)将每个区间视为图的节点重叠的区间建立无向边通过 BFS/DFS 寻找连通分量并合并建图和遍历的开销随节点数呈平方阶增长极端消耗内存暴力双重循环O(n^2)O(n)连续比对任意两个区间若重叠则原地合并重复扫描直到无新合并发生存在大量重复的边界比对和数组元素移动操作排序 贪心双指针当前解法O(n log n)O(log n) 或 O(n)利用快排确立左边界单调性随后通过单次线性扫描动态维护右边界极限时间效率受限于排序算法的基础开销T(n) n log n三、 核心控制流逻辑推导当前源码的执行逻辑基于一个不断维护的动态结果集ans。遍历整个排序后的数组时核心决策分支如下1. 冲突判定cur[0] ans.get(n - 1)[1]成立存在重叠此时说明当前区间cur的起点已经深入到了结果集中最后一个区间last的内部。根据贪心策略这两个区间必须进行物理合并。边界更新机制合并后的新区间起点保持last[0]不变因为排序保证了last[0] cur[0]而其新的右边界则取决于两者的最大伸展范围即执行last[1] Math.max(last[1], cur[1])。为什么必须使用 Math.max因为存在区间完全包含的物理情况。例如区间 A [1, 4] 和区间 B [2, 3]在进行合并时B 完全被 A 包裹合并后的右边界应当保持为 4而不是错误地更替为 3。2. 独立判定cur[0] ans.get(n - 1)[1]不成立互不相交此时说明当前区间cur的起点已经严格大于结果集中最后一个区间的终点。在空间物理分布上两者之间存在断层。入队机制由于后续的所有区间左端点都必然大于或等于cur[0]因此历史区间last已经不可能再与后续的任何区间发生交集last的状态彻底锁定。此时直接将cur作为全新的独立区间压入结果集ans的末尾。四、 算法执行状态机步进示例以输入数据intervals [[2,6], [1,3], [15,18], [8,10]]为例算法内部变量与结果集的动态演进过程如下表所示步骤操作类型/当前区间 cur结果集 ans 当前状态触发条件判断执行核心动作预处理整体排序[]按左端点递增快排排序后序列变为[[1,3], [2,6], [8,10], [15,18]]1扫描[1,3][]结果集为空 (n 0)直接作为基础区间压入。ans [[1,3]]2扫描[2,6][[1,3]]cur[0](2) last[1](3)为True发生重叠更新右边界max(3,6) 6。ans [[1,6]]3扫描[8,10][[1,6]]cur[0](8) last[1](6)为False互不相交作为独立区间追加。ans [[1,6], [8,10]]4扫描[15,18][[1,6], [8,10]]cur[0](15) last[1](10)为False互不相交作为独立区间追加。ans [[1,6], [8,10], [15,18]]结束转换输出[[1,6], [8,10], [15,18]]遍历指针越界调用toArray将 List 扁平化输出为二维数组五、源码实现class Solution { public int[][] merge(int[][] intervals) { // 边界条件处理若输入为空或单区间无需合并直接返回 if (intervals null || intervals.length 1) { return intervals; } // 核心步骤 1利用 lambda 表达式对二维数组按照左端点下标 0进行升序排序 Arrays.sort(intervals, (p, q) - p[0] - q[0]); // 声明动态列表用于存储合并后的不重叠区间 Listint[] ans new ArrayList(); // 核心步骤 2线性扫描区间集合 for (int[] cur : intervals) { int n ans.size(); // 如果结果集不为空且当前区间的左端点小于或等于结果集中最后一个区间的右端点 if (n 0 cur[0] ans.get(n - 1)[1]) { // 说明发生空间重叠贪心更新最后一个区间的右端点为两者的最大值 ans.get(n - 1)[1] Math.max(ans.get(n - 1)[1], cur[1]); } else { // 说明属于独立区间无重叠发生直接追加至结果集末尾 ans.add(cur); } } // 将动态列表转换为标准的二维整型数组返回 return ans.toArray(new int[ans.size()][]); } }六、 复杂度极限分析1. 时间复杂度O(n log n)主导因素算法由排序和线性扫描两部分组成。排序阶段Arrays.sort底层对引用类型包括二维数组的行节点通常采用优化后的 TimSort双轴快排/归并变种其期望时间复杂度为 O(n log n)其中 n 为区间总数。线性扫描阶段for循环遍历长度为 n 的数组内部操作皆为常数级别的指针移动与数值比较耗时 O(n)。结论总体时间复杂度由排序开销主导综合表现为 O(n log n)。2. 空间复杂度O(log n) 或 O(n)分析开销排序产生的栈空间排序算法在执行递归时需要开辟栈帧空间TimSort/QuickSort 的平均辅助空间复杂度为 O(log n)。结果集空间在最坏的物理情况下所有区间彼此互不相交完全独立动态列表ans需要完整存储 n 个区间记录耗费 O(n) 空间。若将返回结果所需的数组空间视为出参则算法纯额外辅助空间为 O(log n)。结论排除返回对象占用的内存额外算法空间复杂度稳定在 O(log n) 阶。