05 August 2008
Given a collection of intervals, merge all overlapping intervals.
Example 1:
1
2
3
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:
1
2
3
Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considerred overlapping.
要求合并区间，可以对区间集进行自定义的排序，按照start的值从小到大排序，排完序后开始合并，首先初始化为第一个区间的start和end，然后从开始遍历，如果遍历到的区间和当前区间无重叠，直接将区间存入到结果中；如果有重叠，将结果中最后一个区间的end值更新为这个end值和遍历到的end值之间的较大值，直至结束。排序的时间是主要的指数， O(n log(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
29
30
31
32
33
34
35
36
37
38
39
40
/**
* 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; }
* }
*/
class Solution {
public List<Interval> merge(List<Interval> intervals) {
if (intervals.size() <= 1) {
return intervals;
}
//Java8的函数式编程
intervals.sort(Comparator.comparingInt(i -> i.start));
List<Interval> result = new LinkedList<>();//链表保持顺序
//初始化
int start = intervals.get(0).start;
int end = intervals.get(0).end;
for (Interval interval : intervals) {
if (interval.start <= end) {//遍历到的interval的start小于之前的end，有重叠,先延伸
end = Math.max(end, interval.end);
} else {//没有重叠，将当前的interval加入到结果集
result.add(new Interval(start, end));
//加入之前的区间后，把start和end更新为当前遍历到的interval的start和end
start = interval.start;
end = interval.end;
}
}
//最后的一个区间没有遍历到的interval比较，需要加入
result.add(new Interval(start, end));
return result;
}
}
题目输入变了，变成了一个二维数组而不是一个class，更新解法：
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
class Solution {
public int[][] merge(int[][] intervals) {
if (intervals.length <= 1) {
return intervals;
}
// Ascending order
Arrays.sort(intervals, Comparator.comparingInt(i0 -> i0[0]));
List<int[]> result = new ArrayList<>();
int[] newInterval = intervals[0]; // newInterval用来记录已经合并和待合并的区间
result.add(newInterval); // 每次都来检查结果集中的最后一个区间
// 遍历每一个二维数组，比较已经合并的区间的尾和新遍历到的头
for (int[] interval : intervals) {
if (interval[0] <= newInterval[1]) { // 当前遍历到的区间的头和已经合并的区间的尾
newInterval[1] = Math.max(newInterval[1], interval[1]); // 更新已合并的区间的尾
} else { // 断了
newInterval = interval;
result.add(newInterval);
}
}
return result.toArray(new int[result.size()][]);
}
}
也可以一个PriorityQueue，先把所有intervals放入到pq中（排好序），然后每次从pq和结果数组各取一个interval出来，一个是当前，一个是之前，二者比较头尾，如果合并，就把结果数组中的之前的数组删除，合并二者创建一个新的interval然后放入到结果数组中；如果不合并，就直接把pq中弹出来的interval加入result中，直到pq中不再有区间为止。
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
class Solution {
public int[][] merge(int[][] intervals) {
List<int[]> result = new ArrayList<>();
if (intervals == null || intervals.length == 0) {
return intervals;
}
PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> o1[0] - o2[0]); // ascending order of start times
for (int[] interval : intervals) { // 所有数据加入pq中
queue.add(interval);
}
result.add(queue.poll()); // 初始数据
while (queue.size() != 0) {
int[] current = queue.poll();
int[] prev = result.get(result.size() - 1);
if (prev[1] >= current[0]) { // this means merge current and prev interval
result.remove(result.get(result.size() - 1));
result.add(new int[]{prev[0], Math.max(prev[1], current[1])});
} else {
result.add(new int[]{current[0], current[1]}); // put the current interval as it is
}
}
return result.toArray(new int[result.size()][]);
}
}