My Java solution 40ms with explanation


  • 0
    S

    First, we sort points depend on their start;

    Then, we set "end" at the first balloon's end,
    we need at least 1 arrow to shot the first balloon.
    for any balloon which start not exceed the current "end"
    we only need that one shot to burst them all.

    But there exist some balloon which start not exceed the current "end",
    but end less than current "end"
    so we can set this balloon's end as current "end".

    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 Integer.compare(o1[0], o2[0]);
    		}
    	});
    	int count = 1, id = 1;
    	int end = points[0][1];
    	while (id < points.length) {
    		if (points[id][0]>end){
    			count++;
    			end = points[id][1];
    		}else if (points[id][1]<end){
    			end = points[id][1];
    		}
    		id++;
    	}
    	return count;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.