合并区间

题意

给出若干闭合区间,合并所有重叠的部分。

样例

给出若干闭合区间,合并所有重叠的部分。

[                     [
  [1, 3],               [1, 6],
  [2, 6],      =>       [8, 10],
  [8, 10],              [15, 18]
  [15, 18]            ]
]

思路

题目没有说是有序的集合,所以我们要进行先根据左端点进行排序,排序后,判断右端点与下一个节点的左端点的大小来决定是否合并区间。

代码实现

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
37
38
/**
* Definition of Interval:
* public class Interval {
* int start, end;
* Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
*/

class Solution {
/**
* @param intervals, a collection of intervals
* @return: A new sorted interval list.
*/
public List<Interval> merge(List<Interval> intervals) {
List<Interval> ans = new ArrayList<Interval>();

Collections.sort(intervals, new Comparator<Interval>(){
@Override
public int compare(Interval obj1, Interval obj2){
return obj1.start - obj2.start;
}
});

Interval last = null;
for (Interval item : intervals) {
if (last == null || last.end < item.start) {
ans.add(item);
last = item;
} else {
last.end = Math.max(last.end, item.end);
}
}

return ans;
}
}

原题地址

LintCode:合并区间

坚持原创技术分享,您的支持将鼓励我继续创作!