Tried to make the solution similar to merge interval problem using Java and min heap


  • 0
    T
    public class Solution {
        class Interval{
            int start;
            int end;
            
            Interval(int start, int end){
                this.start = start;
                this.end = end;
            }
        }
        public int findMinArrowShots(int[][] points) {
            if(points == null || points.length == 0) return 0;
            PriorityQueue<Interval> pq = new PriorityQueue<>(new Comparator<Interval>(){
               public int compare(Interval a, Interval b){
                   if(a.start == b.start) return a.end - b.end;
                   else return a.start-b.start;
               } 
            });
            for(int i = 0;i<points.length;i++){
                pq.add(new Interval(points[i][0], points[i][1]));
            }
            int minArrows = 1;
            Interval temp = pq.poll();
            int end = temp.end;
            while(!pq.isEmpty()){
                Interval curr = pq.poll();
                if(curr.start<=end){
                    //shoot at a common point in both the intervals. which is min(end, curr.end)
                    //for example 1,6 and 2,8 ..so shoot at 6 which is covered by both.
                    end = Math.min(end, curr.end);
                }else{
                    
                    //you need a new arrow for this one buddy.
                    minArrows++;
                    end = curr.end;
                }
            }
            return minArrows;
        }
    }

Log in to reply
 

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