。
算法分为以下几个步骤：
- 将初始所有区间按起始值排序，准备加入数组列表。
- 设立一个数组列表，这个数组列表内保存的是已经按起始值大小排好序的，没有交叉的区间。
那么数组列表末尾是起始值最大的区间。
- 当新元素加入数组列表时，与末尾元素比较，如果有交叉，就修改末尾元素区间。
- 当新元素加入数组列表时，如果与末尾元素比较没有交叉，就直接加入数组列表中。
那么会不会出现新元素和栈内多个元素都交叉呢？不会的，因为如果与多个元素交叉，这里假设末尾元素为S0S_0style="margin-right:
0.0576em;">S
style="height:
0.05em;">0
style="height:
0.15em;">
，那么必然与倒数第二个元素S1S_1style="margin-right:
0.0576em;">S
style="height:
0.05em;">1
style="height:
0.15em;">
相交，设新元素为SSstyle="margin-right:
0.0576em;">S
，那么必然有以下关系式：/>S[0]≤S1[1]S1[1]<S0[0]
S[0]<S0[0]
0.0576em;">S[0]≤style="margin-right:
0.0576em;">S
style="height:
0.05em;">1
style="height:
0.15em;">
[1]style="margin-right:
0.0576em;">S
style="height:
0.05em;">1
style="height:
0.15em;">
[1]<style="margin-right:
0.0576em;">S
style="height:
0.05em;">0
style="height:
0.15em;">
[0]⟹style="margin-right:
0.0576em;">S
[0]<style="margin-right:
0.0576em;">S
style="height:
0.05em;">0
style="height:
0.15em;">
[0]/>那么新元素要比末尾元素S0S_0style="margin-right:
0.0576em;">S
style="height:
0.05em;">0
style="height:
0.15em;">
提前入栈，不符合按起始值顺序加入的假设。
/>
Java实现
packagecn.edu.necpu.problem;importjava.util.*;publicclassIntervalMerger{publicstaticList<int[]>mergeWithStack(int[][]intervals){List<int[]>result=newArrayList<>();if(intervals==null||intervals.length==0){returnresult;}//按照区间的起始位置进行升序排序
Arrays.sort(intervals,Comparator.comparingInt(a->a[0]));//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(nlogn)O(n
\log
0.0278em;">O(nlostyle="margin-right:
0.0139em;">g
n)
- 排序开销
(O(nlogn)O(n
\log
0.0278em;">O(nlostyle="margin-right:
0.0139em;">g
n))
： - 扫描合并开销
(O(n)O(n)style="margin-right:
0.0278em;">O
(n))
： - 总体计算：
- 总时间复杂度
=
=O(nlogn)+O(n)O(n
\log
0.0278em;">O(nlostyle="margin-right:
0.0139em;">g
n)+style="margin-right:
0.0278em;">O
(n)。
- 根据大
表示法的规则，低阶项和常数系数可以忽略，因此最终的时间复杂度由排序主导，即O(nlogn)O(n
\log
0.0278em;">O(nlostyle="margin-right:
0.0139em;">g
n)。
💾
空间复杂度：O(1)O(1)style="margin-right:
0.0278em;">O
(1)或O(n)O(n)style="margin-right:
0.0278em;">O
(n)
空间复杂度的分析取决于我们如何定义“额外空间”：
如果不考虑排序使用的空间：
如果考虑排序使用的空间：
总结：
- 时间复杂度：O(nlogn)O(n
\log
0.0278em;">O
(nlostyle="margin-right:
0.0139em;">g
n)（排序是瓶颈）。 - 空间复杂度：O(1)O(1)
style="margin-right:
0.0278em;">O
(1)（仅指算法使用的额外变量，不包括结果存储和排序栈空间）。
