LeetCode 452：用最少数量的箭引爆气球（贪心）

曾经终败给现在 2024-04-07 13:22 154阅读 0赞

链接

题目：
在这里插入图片描述

方法一：贪心

思路：

按照区间的end进行排序，
如果下一个区间的start > 上一个区间的x_end，则不重叠，可以放入x，count++；
所有不重叠的个数即为需要的弓箭数量；

注意：

存在用例：[[-2147483646,-2147483645],[2147483646,2147483647]]
当compare在比较时，int会溢出！
所以用 Integer.compare()
这里是start > x_end ，没有等号；

Java实现：

class Solution {
    public int findMinArrowShots(int[][] points) {
        // 贪心 ，即求不重叠的区间个数！
        // 先排序
        Arrays.sort(points,new Comparator<int[]>(){
             @Override
             public int compare(int[] a,int[] b){
                 return Integer.compare(a[1],b[1]);
             }
        });
        // 筛选出不重叠的
        int x_end=points[0][1];
        int count=1;
        for(int i=1;i<points.length;i++){
            int start=points[i][0];
            if(start > x_end){
                count++;
                x_end=points[i][1];
            }
        }
        return count;
    }
}