# Java greedy solution using stack;

• 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];
}
}});
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;
}
}``````

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

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