Minimum Number of Arrows to Burst Balloons


  • 0
    A

    class Solution {
    public int findMinArrowShots(int[][] points) {
    if(points.length==0)
    return 0;
    Coordinates [] coOrdinates = new Coordinates [points.length];
    for(int i=0;i<points.length;i++){
    coOrdinates[i] = new Coordinates(points[i][0],points[i][1]);
    }

        Arrays.sort(coOrdinates, new Comparator<Coordinates>(){
            public int compare(Coordinates c1, Coordinates c2){
                return c1.end - c2.end;
            }
        });
        
        int arrowCount  =1;
        PriorityQueue<Coordinates> queue =  new PriorityQueue<Coordinates>();
        queue.offer(coOrdinates[0]);
        
        int coordinateCounter =0 ;
        
        while(!queue.isEmpty()){
            Coordinates stratCoordinate = queue.peek();
            Coordinates currentCoordinate = coordinateCounter+1<coOrdinates.length?coOrdinates[coordinateCounter+1]:null;
            
            if(currentCoordinate==null){                
                break;
            }
            
            if(currentCoordinate.start<=stratCoordinate.end){
                coordinateCounter++;
                continue;
            }else{
                queue.poll();
                queue.offer(currentCoordinate);
                arrowCount++;
            }
            
        }
        
        return arrowCount;
    }
    

    }

    class Coordinates{
    int start;
    int end;

    public Coordinates(int point1,int point2){
        this.start = point1;
        this.end = point2;
    }
    

    }


Log in to reply
 

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