当前位置：首页 > news >正文

合并区间问题

news 2026/5/11 22:19:54

题目描述

合并区间
输入：[[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

算法步骤

这个问题，首先想到的是用数组列表来解决问题。算法分为以下几个步骤：

将初始所有区间按起始值排序，准备加入数组列表。
设立一个数组列表，这个数组列表内保存的是已经按起始值大小排好序的，没有交叉的区间。那么数组列表末尾是起始值最大的区间。
当新元素加入数组列表时，与末尾元素比较，如果有交叉，就修改末尾元素区间。
当新元素加入数组列表时，如果与末尾元素比较没有交叉，就直接加入数组列表中。

那么会不会出现新元素和栈内多个元素都交叉呢？不会的，因为如果与多个元素交叉，这里假设末尾元素为S0S_0S0，那么必然与倒数第二个元素S1S_1S1相交，设新元素为SSS，那么必然有以下关系式：
S[0]≤S1[1]S1[1]<S0[0] ⟹ S[0]<S0[0] S[0] \le S_1[1]\\ S_1[1] \lt S_0[0]\\ \implies S[0]\lt S_0[0]S[0]≤S1[1]S1[1]<S0[0]⟹S[0]<S0[0]
那么新元素要比末尾元素S0S_0S0提前入栈，不符合按起始值顺序加入的假设。

Java实现

packagecn.edu.necpu.problem;importjava.util.*;publicclassIntervalMerger{publicstaticList<int[]>mergeWithStack(int[][]intervals){List<int[]>result=newArrayList<>();if(intervals==null||intervals.length==0){returnresult;}// 1. 按照区间的起始位置进行升序排序Arrays.sort(intervals,Comparator.comparingInt(a->a[0]));// 2. 使用 ArrayList 作为容器ArrayList<int[]>list=newArrayList<>();for(int[]current:intervals){// 如果为空，或者没有交叉，就直接加入数组列表中。if(list.isEmpty()||list.get(list.size()-1)[1]<current[0]){list.add(current);}else{// 如果有重叠，合并区间：更新末尾元素的结束位置int[]top=list.get(list.size()-1);intnewEnd=Math.max(top[1],current[1]);// 末尾元素的结束位置top[1]=newEnd;}}returnlist;}// 测试代码publicstaticvoidmain(String[]args){int[][]intervals={{1,3},{2,6},{8,10},{15,18}};List<int[]>merged=mergeWithStack(intervals);System.out.println("测试用例1");for(int[]interval:merged){System.out.println("["+interval[0]+","+interval[1]+"]");}intervals=newint[][]{{1,3},{2,6},{8,10},{1,18}};merged=mergeWithStack(intervals);System.out.println("测试用例2");for(int[]interval:merged){System.out.println("["+interval[0]+","+interval[1]+"]");}}}

测试结果

测试用例1[1,6][8,10][15,18]测试用例2[1,18]

复杂度分析

这道题的复杂度分析主要取决于排序，这也是整个算法的性能瓶颈。我们可以从时间与空间两个维度来具体拆解：

⏱️ 时间复杂度：O(nlog⁡n)O(n \log n)O(nlogn)

排序开销 (O(nlog⁡n)O(n \log n)O(nlogn))：
- 算法首先调用了Arrays.sort()对区间数组进行排序。在 Java 中，对于原始数据类型或对象数组的排序通常采用优化的快速排序或归并排序，其平均时间复杂度为O(nlog⁡n)O(n \log n)O(nlogn)。
扫描合并开销 (O(n)O(n)O(n))：
- 排序完成后，我们只需要对数组进行一次线性遍历。在遍历过程中，对于每个区间，我们只进行一次比较操作（检查与结果列表末尾区间的重叠情况）以及可能的更新操作（修改末尾区间的结束位置）。
- 这些操作（get、比较、赋值）都是常数时间O(1)O(1)O(1)的，遍历nnn个元素的总时间就是O(n)O(n)O(n)。
总体计算：
- 总时间复杂度 = 排序时间 + 遍历时间 =O(nlog⁡n)+O(n)O(n \log n) + O(n)O(nlogn)+O(n)。
- 根据大 O 表示法的规则，低阶项和常数系数可以忽略，因此最终的时间复杂度由排序主导，即O(nlog⁡n)O(n \log n)O(nlogn)。

💾 空间复杂度：O(1)O(1)O(1)或O(n)O(n)O(n)

空间复杂度的分析取决于我们如何定义“额外空间”：

如果不考虑排序使用的空间：
- 我们只使用了一个ArrayList来存储结果。虽然我们在代码中创建了list，但这是用于存储输出结果的，通常不被视为“额外”的辅助空间。
- 除此之外，我们只使用了常数个临时变量（如current,top,newEnd等）。
- 因此，在这种计算方式下，额外空间复杂度为O(1)O(1)O(1)。
如果考虑排序使用的空间：
- Java 的Arrays.sort()对于对象（如int[]）的排序，在最坏情况下（虽然现代实现会优化）可能需要O(log⁡n)O(\log n)O(logn)到O(n)O(n)O(n)的递归栈空间。
- 此外，如果输入数据不能被修改，我们需要创建副本，这需要O(n)O(n)O(n)的空间。
- 因此，更严谨的总空间复杂度通常是O(n)O(n)O(n)（主要由排序算法的栈空间或结果存储决定）。