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

  • 0
    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;
                Interval curr = pq.poll();
                    //shoot at a common point in both the intervals. which is min(end, curr.end)
                    //for example 1,6 and 2,8 shoot at 6 which is covered by both.
                    end = Math.min(end, curr.end);
                    //you need a new arrow for this one buddy.
                    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.