Java greedy solution using stack;


  • 1

    The main idea is we burst balloons from left to right. For example: for balloons (1,6) , (2,8) , (7,12) , (10,16) (after sort). From left to right we can find there is a overlap (2, 6) between (1,6) and (2,8) , then for(2,6) and (7,12), no overlap, so burst the first two balloons and so on...

    public class Solution {
        public int findMinArrowShots(int[][] points) {
            if(points == null || points.length <= 1) {
                return points.length;
            }
            int res = 0;
            Arrays.sort(points , new Comparator<int[]>() {
                public int compare(int[] p1 ,int[] p2) {
                    if(p1[0] != p2[0]) {
                        return p1[0] - p2[0];
                    }else {
                        return p1[1] - p2[1];
                    }
                }});
            LinkedList<int[]> stack = new LinkedList<int[]>();
            for(int[] p : points) {
                if(stack.isEmpty()) {
                    stack.push(p);
                }else {
                    int[] temp = merge(stack.peek() , p);
                    if(temp != null) {
                        stack.pop();
                        stack.push(temp);
                    }else {
                        stack.pop();
                        res++;
                        stack.push(p);
                    }
                }
            }
            return stack.isEmpty() ? res : res + 1;
            
        }
        
        protected int[] merge(int[] p1 , int[] p2) {
            if(p1[1] >= p2[0]) {
                int[] res = new int[2];
                res[0] = Math.max(p1[0] , p2[0]);
                res[1] = Math.min(p1[1] , p2[1]);
                return res;
            }
            return null;
        }
    }

  • 0
    K

    Nice solution! Do you mind explaining why you've used a LinkedList<> stack instead of just Stack<> is there a benefit to this? Thanks!


Log in to reply
 

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