Java O(nlogn) Simple solution


  • 0
    H

    The idea is to sort the balloons based on its starting point. ( Works the other way as well).

    Put an arrow at the starting point of the last balloon and skip the balloons which has its ending point >= prev arrow.
    Increment the arrow count when you see the prev condition fail. Repeat.

    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 arrows=0,i=points.length-1, x=0;
            while(i>=0){
                x=points[i][0];
                while(--i>=0 && x<=points[i][1]);
                arrows++;
                   
            }
            return arrows;
        }
    

Log in to reply
 

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