DEV Community

Prashant Mishra
Prashant Mishra

Posted on

Minimum No. of arrows to burst balloons

Problem

class Solution {
    public int findMinArrowShots(int[][] points) {
        //remove all the overlapping baloons 
        //this will lead to only baloons that are not overlapping
        //and we will need at min that many arros to burst them


        //step1 : sort the give points in ascending order of Xend
        Arrays.sort(points,(a,b)-> Integer.compare(a[1],b[1]));
        //step2: get the count of non overlapping intervals and that will the no. of arrows we will need
        int xstart = points[0][0];
        int xend = points[0][1];
        int count =1;// atleast one arrow is needed to burst baloon(s)
        for(int i =1;i<points.length;i++){
            if(xend < points[i][0]){// xend is less than than the xstart of next baloon hence they are not overlapping
                count++;
                xend = points[i][1]; //update xend
            }
        }
        return count;
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)