Java O(nlogn) Simple solution

  • 0

    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[]>() {
            public int compare(int[] o1, int[] o2) {
                 return[0], o2[0]);
            int arrows=0,i=points.length-1, x=0;
                while(--i>=0 && x<=points[i][1]);
            return arrows;

Log in to reply

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