Approach 1: Greedy
Idea:
We know that eventually we have to shoot down every balloon, so for each ballon there must be an arrow whose position is between balloon[0] and balloon[1] inclusively. Given that, we can sort the array of balloons by their ending position. Then we make sure that while we take care of each balloon in order, we can shoot as many following balloons as possible.
So what position should we pick each time? We should shoot as to the right as possible, because since balloons are sorted, this gives you the best chance to take down more balloons. Therefore the position should always be balloon[i][1] for the ith balloon.
This is exactly what I do in the for loop: check how many balloons I can shoot down with one shot aiming at the ending position of the current balloon. Then I skip all these balloons and start again from the next one (or the leftmost remaining one) that needs another arrow.
// JAVA
public int findMinArrowShots(int[][] points) {
if (points.length == 0) {
return 0;
}
Arrays.sort(points, (a, b) -> a[1] - b[1]); // sort by the ending position
int arrowPos = points[0][1];
int arrowCnt = 1;
for (int i = 1; i < points.length; i++) {
if (arrowPos >= points[i][0]) {
continue;
}
arrowCnt++;
arrowPos = points[i][1];
}
return arrowCnt;
}
Time complexity: O(nlogn)
Approach 2: Greedy
The greedy idea is similar to the one above. Instead of sorting by the ending position, you can also sort by the starting position but it would then require additional checks.
// C++
int findMinArrowShots(vector<vector<int>>& points) {
// sanity check
if (points.size()==0)
return 0;
sort(points.begin(), points.end());
int res = 1, end = points[0][1];
for (int i=1; i<points.size(); i++) {
if (points[i][0]>end) {
end = points[i][1];
res++;
} else {
end = min(end, points[i][1]);
}
}
return res;
}
Time complexity: O(nlogn)