Google
56 Merge Intervals

1. Question

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

2. Implementation

(1) Scan Line
1
/**
2
* Definition for an interval.
3
* public class Interval {
4
* int start;
5
* int end;
6
* Interval() { start = 0; end = 0; }
7
* Interval(int s, int e) { start = s; end = e; }
8
* }
9
*/
10
class Solution {
11
public List<Interval> merge(List<Interval> intervals) {
12
List<Interval> res = new ArrayList<>();
13
14
if (intervals == null || intervals.size() == 0) {
15
return res;
16
}
17
18
Collections.sort(intervals, new Comparator<Interval>() {
19
@Override
20
public int compare(Interval i1, Interval i2) {
21
return i1.start - i2.start;
22
}
23
});
24
Interval preInterval = null;
25
26
for (Interval curInterval : intervals) {
27
if (preInterval == null || preInterval.end < curInterval.start) {
28
res.add(curInterval);
29
preInterval = curInterval;
30
}
31
else if (preInterval.end < curInterval.end) {
32
preInterval.end = curInterval.end;
33
}
34
}
35
return res;
36
}
37
}
Copied!

3. Time & Space Complexity

Scan Line: 时间复杂度O(nlogn), 空间复杂度O(n)