合并区间

题目内容:给出一组区间,请合并所有重叠的区间。请保证合并后的区间按区间起点升序排列。很好理解,就是将给定区间中相交的区间进行合并,并且按照起点进行升序排列。

例子:

输入:[[10,30],[20,60],[80,100],[150,180]]

返回值:[[10,60],[80,100],[150,180]]

在做之前我们先思考一下,需要合并区间的情况有多少种(待扩张区间:我们将选中区间与该区间进行合并;选中区间:当前选取的区间):

  • 待扩张区间选中区间起点重合
    • 选中区间的结束点 <= 待扩张区间终点,这种情况说明待扩张区间的范围要大于选中区间,因此不需要进行处理。
    • 选中区间的结束点>待扩张区间终点,这种情况,需要将选中区间与待扩张区间进行合并,由于起点是重合的,因此只需要将待扩张区间的结束点修改为选中区间的结束点即可。
  • 待扩张区间选中区间起点不重合(这里指选中区间的起点均大于等于待扩张区间)
    • 选中区间的起点和终点 <= 待扩张区间的结束点,即选中区间被包含在待扩张区间内。
    • 选中区间的起点在待扩张区间的终点前,但选中区间的终点在区间的终点后。
    • 选中区间的起点等于待扩张区间的终点,即两个区间刚好接壤。
    • 选中区间的起点大于待扩张区间的终点,即两个区间不相交。

上面的条件看起来可能比较抽象,并且不易于理解,我们通过下面这张图来直观地体会上述条件,图中两条线中上面为待扩张区间,下面为选中区间。(橙色的线是为了让线看起来没那么难受-_-||,今后的文章中,我将会使用PPT来画图、制作动画进行解析)

合并区间条件
合并区间条件

由图可见,起点相同的情况只有第三种需要进行合并,起点不同的情况只有第三、四种需要进行合并,第五种则将选中区间作为下一个待扩张区间。除此之外,由于原给定区间是无序的,处理起来不是很方便,我们需要以区间的起点进行排序,再做后续的合并操作。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import java.util.*;
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
public class Solution {
public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
Collections.sort(intervals, (o1, o2) -> {
return o1.start - o2.start;
});
Deque<Interval> queue = new LinkedList<>();
for(int i = 0; i < intervals.size(); i++) {
if(queue.isEmpty()) {
queue.offer(intervals.get(i));
} else {
Interval itv = queue.peekLast();
Interval interval = intervals.get(i);
if(itv.start == interval.start) {
itv.end = Math.max(itv.end, interval.end);
} else {
if(itv.end < interval.start) { // 两个区间不相交
queue.offer(interval);
} else {
itv.end = Math.max(interval.end, itv.end);
}
}
}
}
return new ArrayList<>(queue);
}
}

我们将第一个区间作为待扩张区间,接下来将剩余的区间都与待扩张区间进行比对,将满足条件的区间融入待扩张区间,完成合并操作。由于预先进行了排序处理,因此所有后面的区间的起点均大于等于前面的起点,这样处理起来就非常方便了。当起点重合时,将待扩张区间的终点值设置为两个区间中最大值即可。起点不重合时,看看两者是否相交,不相交则将该区间作为下一个待扩张区间;相交则将待扩张区间的终点值设置为两个区间中最大值。