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

链接

题目：

方法一：贪心

思路：

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

注意：

1. 存在用例 ：[[-2147483646,-2147483645],[2147483646,2147483647]]
   当compare在比较时，int会溢出！
   所以用 Integer.compare()
2. 这里是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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24