Difficulty: Medium
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 considered overlapping.
|
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
Solution
Language: Java
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
| class Solution {
public int[][] merge(int[][] intervals) {
if (intervals == null || intervals.length == 0 || intervals[0].length == 0) {
return intervals;
}
List<int[]> list = new ArrayList<>();
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
int start = intervals[0][0];
int end = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
int[] interval = intervals[i];
if (end >= interval[0]) {
end = Math.max(end, interval[1]);
} else {
list.add(new int[]{start, end});
start = interval[0];
end = interval[1];
}
}
list.add(new int[]{start, end});
int[][] result = new int[list.size()][2];
for (int i = 0; i < result.length; i++) {
result[i] = list.get(i);
}
return result;
}
}
|