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].

定义区间类Interval

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Interval{
private int start;
private int end;
Interval(){
start = 0;
end = 0;
}
Interval(int start, int end){
this.start = start;
this.end = end;
}
public int getStart(){
return start;
}
public int getEnd(){
return end;
}
}

定义比较器IntervalComparator,比较区间起始位置的大小,方便对区间线性表进行排序

1
2
3
4
5
6
7
import java.util.*;
public class IntervalComparator implements Comparator<Interval> {
public int compare(Interval i1, Interval i2) {
return i1.getStart() - i2.getStart();
}
}

选用ArrayList作为具体类来存储区间对象,因为提取元素或在线性表的尾部插入和删除元素,ArrayList的效率更高。

  • 相邻的两个区间对象previousnext

  • 如果previous的截止位置大于或等于next的起始位置,则两个区间对象存在重叠部分。这里认为,previous不应该存在next中的内容,即修改previous中的内容。对于定义为ArrayList的结果线性表,即删除尾部元素,处理重叠部分后,重新插入。
    如果previous的截止位置小于next的起始位置,两个区间对象不存在重叠部分,可以将next暂时插入。

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
public ArrayList<Interval> Merge(ArrayList<Interval> intervals){
if(intervals.size() <= 1)
return intervals;
Collections.sort(intervals, new IntervalComparator());
ArrayList<Interval> result = new ArrayList<Interval>();
result.add(new Interval());//修改previous中的内容,需要对结果线性表初始化
Interval previous = intervals.get(0);
for(int i = 1; i < intervals.size(); i++){
Interval next = intervals.get(i);
if(previous.getEnd() >= next.getStart()){
result.remove(result.size() - 1);
Interval current = new Interval(previous.getStart(), Math.max(previous.getEnd(), next.getEnd()));//注意可能的包含关系
previous = current;
}
else{
previous = next;
}
result.add(previous);
}
return result;
}

简单的测试程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void main(String[] args){
ArrayList<Interval> intervals = new ArrayList<Interval>();
intervals.add(new Interval(9, 15));
intervals.add(new Interval(2, 6));
intervals.add(new Interval(12, 14));
intervals.add(new Interval(1, 5));
intervals.add(new Interval(3, 7));
ArrayList<Interval> result = Merge(intervals);
printResult(result);
}
public static void printResult(ArrayList<Interval> result){
for(int i = 0; i < result.size(); i++){
Interval in = result.get(i);
System.out.println("[" + in.getStart() + " " + in.getEnd() + "]");
}
}
输出结果为:
1
2
3
4
1
2
[1 7]
[9 15]

参考资料:

LeetCode – Merge Intervals