BiruLyu
6/26/2017 - 5:06 AM

## 452. Minimum Number of Arrows to Burst Balloons(1st).java

``````public class Solution {
public int findMinArrowShots(int[][] points) {
if (points == null || points.length < 1 || points[0].length < 1) return 0;
Arrays.sort (points, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
if (a[0] == b[0]) return a[1] - b [1];
return a[0] - b[0];
}
});

int count = 1;
int limited = points[0][1];
for (int i = 0; i < points.length; i++) {
int[] cur = points[i];
if (cur[0] <= limited) {
limited = Math.min(limited, cur[1]);
} else {
count++;
limited = cur[1];
}
}
return count;
}
}``````
``````public class Solution {
public int findMinArrowShots(int[][] points) {
//This is obviously greedy problem
//So we need to fire the first arrow such that it bursts as many as possible
//which means we need to sort them in the increasing order of X-end
//So the first arrow needs to be fired at the first balloon's X-end (beyond that the first would not burst)
//So the second arrow needs to be fired only if we encounter a balloon which is starting beyond this X-end
//We ll have to fire the second one on that one's X-end and so on
//Base case
if(points == null || points.length == 0) { //Empty balloons require zero arrows
return 0;
}
//Sort the balloons in increasing order of X-end
Arrays.sort(points, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
return a[1]==b[1] ? a[0]-b[0] : a[1] - b[1];
}
});
//Initially arrow_count is 1
int arrow_count = 1;
//The first arrow needs to be shot at the first balloon's X-end
int arrow_position = points[0][1];
//Iterate thro' the rest of the balloons and fire an arrow only if that balloon's start is beyond the arrow position
for(int i=1; i<points.length; i++) {
if(points[i][0] > arrow_position) {
arrow_count++; //one more arrow needs to be fired
arrow_position = points[i][1]; //needs to be fired at that balloon's X-end
}
}
return arrow_count;
}
}``````