Java Accepted Simple O(nlog(n)) Solution using PriorityQueue


  • 0

    The idea comes from Meeting Room II. Find the location where maximum balloons overlap, shot at this place kills the most balloons. Killing all balloons means clear the PriorityQueue and start again.

        public int findMinArrowShots(int[][] points) {
            if (points.length == 0) return 0;
            Arrays.sort(points, new Comparator<int[]>(){
                public int compare(int[] a, int[] b) {
                    return a[0]-b[0];
                }
            });
            PriorityQueue<int[]> pq = new PriorityQueue(new Comparator<int[]>(){
                public int compare(int[] a, int[] b) {
                    return a[1]-b[1];
                }
            });
            
            int count = 0;
            for (int[] point: points) {
                if (pq.isEmpty() || point[0] <= pq.peek()[1]) {
                    pq.add(point);
                } else {
                    count++;
                    pq.clear();
                    pq.add(point);
                }
            }
            if (!pq.isEmpty()) count++;
            
            return count;
        }

Log in to reply
 

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