【贪心算法】452. 用最少数量的箭引爆气球

452. 用最少数量的箭引爆气球

射击气球的最小箭数

题目描述

给定一系列气球的位置，每个气球由一个开始和结束的坐标点表示。我们射箭时，箭可以在水平线上从左到右无限延伸。问射出的箭头最小数量是多少，才能保证所有的气球都被射中。

解题思路

贪心算法

此题的关键在于利用贪心算法的思想找到一种最优的射箭方式，使得射出的箭数最少。

1. 排序：首先，按照气球的结束坐标进行排序，这样可以保证我们总是优先考虑结束最早的气球，从而尽可能多地让后续的箭覆盖更多的气球。

2. 遍历：遍历排序后的气球数组，对于每一个气球，如果它的开始坐标大于当前记录的结束坐标（表示这个气球和前一个气球不重叠），我们就需要再射出一支箭，并更新当前记录的结束坐标为这个气球的结束坐标。

边界值处理

在处理整数边界值时，为避免直接使用减法比较导致的整数溢出问题，推荐使用Integer.compare()方法进行比较。

代码实现

class Solution {
    public int findMinArrowShots(int[][] points) {
        int n = points.length;
        return intervalSchedule(points);
    }

    // 计算不重叠区间
    int intervalSchedule(int[][] nums){
        if(nums.length == 0){
            return 0;
        }

        // 寻找最早开始的区间
        // 排序
        Arrays.sort(nums,new Comparator<int[]>(){
            public int compare(int[] a,int[] b){
                // return a[1] - b[1];
                return Integer.compare(a[1], b[1]);
            }
        });


        int x_end = nums[0][1];
        int count = 1;

        for(int [] num: nums){
            int start = num[0];

            if(start  > x_end){
                count++;
                x_end = num[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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39