算法-贪心-用最少数量的箭引爆气球

梦里梦外; 2023-05-21 13:58 10阅读 0赞

# 算法-贪心-用最少数量的箭引爆气球 #

# 1 题目概述 #

## 1.1 题目出处 ##

https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons/

## 1.2 题目描述 ##

在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以y坐标并不重要，因此只要知道开始和结束的x坐标就足够了。开始坐标总是小于结束坐标。平面内最多存在104个气球。

一支弓箭可以沿着x轴从不同点完全垂直地射出。在坐标x处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。

Example:

输入:  
\[\[10,16\], \[2,8\], \[1,6\], \[7,12\]\]

输出:  
2

解释:  
对于该样例，我们可以在x = 6（射爆\[2,8\],\[1,6\]两个气球）和 x = 11（射爆另外两个气球）。

# 2 题解 #

## 2.1 贪心法 ##

### 2.1.1 思路 ###

我们贪心的希望每次用一个弓箭手射击到尽可能多的气球：

1.  将气球坐标start end 从小到大排序
2.  排序后，维护一个全局右边界right，只要一个气球左边界小于该全局右边界right，就说明可以用一个弓箭手射击。  
    但还需要判断这个气球右边界是否小于全局右边界，如果小于就需要更新全局右边界
3.  否则，就更新全局右边界，且弓箭手数量加一，表示跟之前右边界不重合，需要新的弓箭手射击

### 2.1.2 代码 ###

class Solution { 
        public int findMinArrowShots(int[][] points) { 
            if(null == points || points.length == 0){ 
                return 0;
            }
    
            // 对气球坐标先按start，相同时再按end排序
            Arrays.sort(points, (o1, o2) -> { 
                if(o1[0] == o2[0]){ 
                    return o1[1] - o2[1];
                }else{ 
                    return o1[0] - o2[0];
                }
            });
    
            int result = 1;
            // 维护右边界
            int right = points[0][1];
            for(int i = 1; i < points.length; i++){ 
                if(points[i][0] <= right){ 
                // 当前记录的左边界小于等于当前全局右边界，说明可以重合
                    if(points[i][1] < right){ 
                        // 当前记录的右边界小于当前全局右边界
                        // 就需要更新全局右边界
                        right = points[i][1];
                    }
                }else{ 
                // 当前记录的左边界大于当前全局右边界，说明无重合，需要新起一个弓箭手
                    right = points[i][1];
                    result++;
                }
            }
            return result;
        }
    }

### 2.1.3 时间复杂度 ###

O(n)  
![在这里插入图片描述][2020041911311613.png]

### 2.1.4 空间复杂度 ###

O(1)

[2020041911311613.png]: /images/20230521/0768834ce67b47ab8dbc938d0eb7c780.png