LeetCode - Merge Intervals
Problem description
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.
Analysis
Basically, if first[1] > second[0], we can merge them, as long as first[0] <= second[0];
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
public int[][] merge(int[][] intervals) {
List<int[]> stack = new ArrayList<>();
if (intervals.length == 0){
return intervals;
}
Arrays.sort(intervals, (o1, o2) -> {
// if (o1[0] == o2[0]){
// return o1[1] - o2[1];
// }
return o1[0] - o2[0];
});
// stack.add(intervals[0]);
int[] last = intervals[0];
for (int i = 1; i < intervals.length; i++){
// int[] last = stack.remove(stack.size() - 1);
if (last[1] >= intervals[i][0]){
// stack.add(new int[]{last[0], Math.max(last[1], intervals[i][1])});
last[1] = Math.max(last[1], intervals[i][1]);
}
else {
stack.add(last);
last = intervals[i];
}
}
// int[][] res = new int[stack.size()][2];
// int index = 0;
// for (int[] i: stack){
// res[index++] = i;
// }
stack.add(last);
return stack.toArray(new int[stack.size()][]);
}
What to improve
- there’s no need to add into list, don’t add.