452. Minimum Number of Arrows to Burst Balloons
Greedy Solution: Sort intervals by ending value; Only count valid intervals we need, and skip overlapping intervals
See the picture in this post to understand the idea behind greedy approach to this problem better.
Similar Questions:
Time = O(nlogn), Space = O(1)
class Solution {
public int findMinArrowShots(int[][] points) {
if (points.length == 0) {
return 0;
}
Arrays.sort(points, new Comparator<int[]>(){
@Override
public int compare(int[] o1, int[] o2) {
return o1[1] - o2[1];
}
});
int minNum = 1;
int[] prePoint = points[0];
for (int i = 1; i < points.length; i++) {
if (prePoint[1] < points[i][0]) {
prePoint = points[i];
minNum ++;
}
}
return minNum;
}
}