Description
Given a collection of intervals, merge all overlapping intervals.
Example
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 considered overlapping.
|
Solution
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
| class Solution {
public int[][] merge(int[][] intervals) {
List<int[]> res = new ArrayList<>();
if (intervals == null || intervals.length == 0) return res.toArray(new int[0][]);
Arrays.sort(intervals, new Comparator<int[]>(){
@Override
public int compare(int[] a, int[] b){
return a[0] - b[0];
}
});
int start = intervals[0][0];
int end = intervals[0][1];
for (int[] interval: intervals){
if (interval[0] <= end){
end = Math.max(end, interval[1]);
}
else{
res.add(new int[]{start, end});
start = interval[0];
end = interval[1];
}
}
res.add(new int[]{start, end});
return res.toArray(new int[res.size()][]);
}
}
|