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

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

[链接][Link 1]

**题目**：  
![在这里插入图片描述][4d029fc9de1546ddb95d533d48d40d76.png]

### 方法一：贪心 ###

**思路：**

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;
        }
    }

[Link 1]: https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/
[4d029fc9de1546ddb95d533d48d40d76.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/2d634fb3c843478a8ac360312c691719.png