452. 用最少数量的箭引爆气球 (opens new window)

1.区间排序+贪心

分析：首先将区间按照左边界值从小到大进行排序。创建一个优先级队列按照右边界值从小到大排序，如果当前区间的左边界大于队列头节点，即队列最小的右边界值，则说明当前队列中的所有气球可以一次性戳爆，队列所有元素移除。

进一步，因为每次出队列是所有元素都移除，所以可以使用一个变量代替小顶堆。如果满足上述射击条件则重置当前最小右区间值，否则持续更新当前最小值。

贪心思想：因为初始化按照左边界排过序，只要队列中有一个区间与当前区间是断开的，那么后面的区间和当前队列也都是断开的。另外只要存在至少一个区间是断开的，则不可能用同一根箭同时引爆。

PS：注意比较器中排序的写法，如果数据范围比较大，计算o1[0] - o2[0]会爆，因此用比较判断的方法较为准确。

class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points,new Comparator<int[]>(){
            public int compare(int[] o1,int[] o2){
                if(o1[0]<o2[0]) return -1;
                else return 1;
            }
        });
        int minright=Integer.MAX_VALUE;
        int res=0;
        for(int i=0;i<points.length;i++){
            boolean move=false;
            if(minright<points[i][0]){
                res++;
                minright=points[i][1];
            }
            minright=Math.min(minright,points[i][1]);
        }
        return res+1;
    }
}