题目要求
1
2
3
4
5
| Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
|
输入一系列区间，将出现交叉的区间合并起来，并将合并后的区间返回。这里需要注意的是，区间的大小顺序无关，即输出为[1,2],[3,4]和[3,4],[1,2]都是可以的
思路一：简单粗暴利用排序API
第一次看到这道题目，难免就会想到，将这些区间按照开始值有小到大排序，然后依次比较前后两个区间的开始值和结束值，如果出现重叠，则将两个区间合并。
在这里先介绍一下，java中的两种利用API进行排序的方法。
当排序对象是数组时，可以使用Arrays.sort机制，它的核心实现在于Comparable接口。任何一个实现了该接口的数组中的成员都可以使用Arrays.sort方法。
当排序对象是集合时，可以使用list.sort方法。它的核心实现在于Comparator接口。通过该接口可以实现集合的排序。
在这里不详细介绍这二者的内核和具体实现，有兴趣的可以查看java API。
代码实现如下：
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
| public List<Interval> merge(List<Interval> intervals) {
List<Interval> result = new ArrayList<Interval>();
if( intervals.size() == 0){
return result;
}
intervals.sort(new Comparator<Interval>(){
@Override
public int compare(Interval o1, Interval o2) {
if(o1.start < o2.start){
return -1;
}else if(o1.start > o2.start){
return 1;
}
return 0;
}
});
result.add(intervals.get(0));
for(int i = 1 ; i<intervals.size() ; i++){
Interval previous = result.get(result.size()-1);
Interval temp = intervals.get(i);
if(temp.start <= previous.end){
previous.end = temp.end > previous.end ? temp.end : previous.end;
}else{
result.add(temp);
}
}
return result;
}
|
思路二：简化排序
对对象的排序其实相当的影响效率和性能。其实这题的问题跳脱出来看，无需知道特定的区间，只要知道所有的按顺序的起始值和终点值。
例如输入为[1,3],[5,6],[2,7]
如果按照思路一，则需要先将对象排序，得出[1,3],[2,7],[5,6],然后再依次判断是否需要合并临近区间。
按照思路二，我们直接将区间看成起始值列表[1,5,2]和结束值列表[3,6,7]。将这两个数组分别排序可以得到[1,2,5]和[3,6,7]。也就是说，**[1,3],[5,6],[2,7]合并后的结果和[1,3],[2,6],[5,7]是等价的**。
为什么呢？因为如果两个区间重叠，那么这两个区间的一个结束值和一个开始值必然不会出现在结果集中，也就是说，我只需要找到这两个区间的一个最小值和一个最大值就可以了。如果是n个区间重叠，那么只要找这n个区间的最小值和最大值就可以了。同理，如果一个区间和任何一个区间都不会发生合并，它的开始值和结束值就必然会在排序后两个数组中处于相同下标的位置。且其结果值一定小于下一个下标的开始值。
按照这种思路，实现的代码如下：
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
| public List<Interval> merge2(List<Interval> intervals) {
if(intervals == null || intervals.size() < 2)
return intervals;
List<Interval> res = new ArrayList<>();
int len = intervals.size();
int[] starts = new int[len], ends = new int[len];
for(int i = 0; i < len; i++){
starts[i] = intervals.get(i).start;
ends[i] = intervals.get(i).end;
}
Arrays.sort(starts);
Arrays.sort(ends);
int start = starts[0], end = ends[0];
for(int i = 0; i < len - 1; i++){
if(ends[i] >= starts[i + 1]){
end = ends[i + 1];
}
else{
end = ends[i];
res.add(new Interval(start, end));
start = starts[i + 1];
end = ends[i + 1];
}
}
res.add(new Interval(start, end));
return res;
}
|
可以看到，该算法的时间复杂度为O(4n)
思路三：无需排序的算法
这个答案参考了一下高分回答。整理了一下思路如下：
其实在这里无需对各个区间排序。只需要将需要合并的区间合并起来即可。如果经过判断是独立的区间，则将该区间加入结果集，如果不是独立的区间，则将该区间合并至后续的区间并继续判断下一个区间在剩余的区间中是否是独立的区间。
举个栗子，输入为[1,3],[5,6],[10,11],[2,7]，
先判断[1,3]是否是独立区间，可见[1,3]可以和[2,7]合并，则将[2,7]修改为[1,7]。
接着判断[5,6]是否可以合并至后面的区间，发现需要将[5,6]与[1,7]合并，合并为[1,7]。
最后，还剩下[10,11]和[1,7]可以先后加入结果集。
代码如下：
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
| public List<Interval> merge3(List<Interval> intervals) {
int size = intervals.size();
if (size < 2) {
return intervals;
}
List<Interval> result = new ArrayList<Interval>(size);
Interval[] array = intervals.toArray(new Interval[size]);
for (int f = 0; f < size; f++) {
Interval first = array[f];
boolean add = true;
for (int s = f + 1; s < size; s++) {
Interval second = array[s];
if (first.end < second.start || first.start > second.end) {
continue;
}
if (first.start <= second.start) {
second.start = first.start;
}
if (first.end >= second.end) {
second.end = first.end;
}
add = false;
break;
}
if (add) {
result.add(first);
}
}
return result;
}
|