-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path0056. Merge Intervals
68 lines (66 loc) · 2.27 KB
/
0056. Merge Intervals
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class Solution {
// public int[][] merge(int[][] intervals) {
// TreeMap<Integer, Integer> tree = new TreeMap<>();
// for(int[] i: intervals){
// if(tree.containsKey(i[0])){
// if(i[1] > tree.get(i[0]))
// tree.put(i[0], i[1]);
// }
// else tree.put(i[0], i[1]);
// }
// if(tree.size() == 1){
// int[][] res = new int[1][2];
// res[0][0] = tree.firstKey();
// res[0][1] = tree.get(tree.firstKey());
// return res;
// }
// ArrayList<List<Integer>> arr = new ArrayList<>();
// for(int i : tree.keySet()){
// arr.add(Arrays.asList(i, tree.get(i)));
// }
// for(int i = 1; i < arr.size(); ){
// int lastEnd = arr.get(i - 1).get(1);
// int currBeg = arr.get(i).get(0);
// int currEnd = arr.get(i).get(1);
// if(currEnd <= lastEnd){
// arr.remove(i);
// }
// else if(currBeg <= lastEnd && lastEnd <= currEnd){
// arr.get(i-1).set(1, currEnd);
// arr.remove(i);
// }
// else{
// i++;
// }
// }
// int[][] res = new int[arr.size()][2];
// int index = 0;
// for(List<Integer> i : arr){
// res[index][0] = i.get(0);
// res[index][1] = i.get(1);
// index++;
// }
// return res;
// }
public int[][] merge(int[][] intervals) {
// if (intervals.length == 0) {
// return intervals;
// }
List<int[]> arr = new ArrayList<>();
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
int[] pre = intervals[0];
for (int i = 0; i < intervals.length; i++) {
int[] curr = intervals[i];
if (curr[0] <= pre[1]) {
pre[1] = Math.max(curr[1], pre[1]);
}
else {
arr.add(pre);
pre = curr;
}
}
arr.add(pre);
//此处0是一个占位符。它最终会被实际的集合大小所替代
return arr.toArray(new int[0][0]);
}
}