-
Notifications
You must be signed in to change notification settings - Fork 1
/
MinimumNumberArrowsBurstBalloons.java
123 lines (94 loc) · 3.5 KB
/
MinimumNumberArrowsBurstBalloons.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
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
package com.leetcode;
import java.util.Arrays;
public class MinimumNumberArrowsBurstBalloons {
/*
Sorting by start need backtracking as we may miss
0 9,0 6,2 9,2 8,3 9,3 8,3 9,6 8,7 12,9 10
0------------------------------------9
0---------------6
2--------------------------------9
2-----------------------------8
3----------------------------9
3-------------------------8
3----------------------------9
6-----------------8
7------------------------12
9---10
Sorting by end helps apply greedy approach to consume interval
0-------------6
3----------8
6----8
2-------------8
3------------9
2---------------9
0--------------------9
3------------9
9--10
7------------12
*/
class Solution {
public int findMinArrowShots(int[][] points) {
if(points == null || points.length == 0) return 0;
Arrays.sort(points,(a, b)->(Integer.compare (a[1] , b[1])));// .compare because testcase has int maxValue
//Arrays.sort(points,(a,b)->(a[1]-b[1]));
int count = 1;
int[] prev = points[0];
for(int i = 1 ; i < points.length ; i++){
int[] next = points[i];
if(isOverlap(prev,next)){
prev[0] = Math.max(prev[0],next[0]);
prev[1] = Math.min(prev[1],next[1]);
}else{
count++;
prev = next;
}
}
return count;
}
public boolean isOverlap(int[] a , int[] b){
if((a[0] > b[1]) || (b[0] > a[1])) return false; // one is starting after other ends then no overlap
return true;
}
}
class Solution2 {
public int findMinArrowShots(int[][] points) {
if(points.length <= 1) return points.length;
//sort by end time
Arrays.sort(points,(a, b)->(Integer.compare (a[1] , b[1])));// .compare because testcase has int maxValue
int count = 1;
int [] prev = points[0];
for(int i = 0 ; i < points.length ; i++){
int start = prev[0];
int end = prev[1];
int next[] = points[i];
if(next[0] > prev[1] || next[1] < prev[0]){//no overlap
count++;
prev = next; // as next[1] is greater
}
}
return count;
}
}
}
//Alternate sort by start time
public int findMinArrowShots(int[][] points) {
if(points.length <= 1) return points.length;
//sort by end time
Arrays.sort(points,(a, b)->(Integer.compare (a[0] , b[0])));// .compare because testcase has int maxValue
int count = 1;
int [] prev = points[0];
for(int i = 0 ; i < points.length ; i++){
int start = prev[0];
int end = prev[1];
int next[] = points[i];
if(next[0] > prev[1]){//no overlap
count++;
prev = next;
}else{
prev[0] = Math.max(prev[0], points[i][0]);
prev[1] = Math.min(prev[1], points[i][1]);
}
}
return count;
}
}