博客昵称：沈小农学编程
作者简介：一名在读硕士，定期更新相关算法面试题，欢迎关注小弟！
PS：哈喽！各位CSDN的uu们，我是你的小弟沈小农，希望我的文章能帮助到你。欢迎大家在评论区唠嗑指正，觉得好的话别忘了一键三连哦！😘
题目难度：中等
默认优化目标：最小化时间复杂度。
Python默认为Python3。
目录
1 题目描述
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 x``start，x``end， 且满足 xstart ≤ x ≤ x``end，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。
给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。
示例 1：
输入：points = [[10,16],[2,8],[1,6],[7,12]] 输出：2 解释：气球可以用2支箭来爆破: -在x = 6处射出箭，击破气球[2,8]和[1,6]。 -在x = 11处发射箭，击破气球[10,16]和[7,12]。示例 2：
输入：points = [[1,2],[3,4],[5,6],[7,8]] 输出：4 解释：每个气球需要射出一支箭，总共需要4支箭。示例 3：
输入：points = [[1,2],[2,3],[3,4],[4,5]] 输出：2 解释：气球可以用2支箭来爆破: - 在x = 2处发射箭，击破气球[1,2]和[2,3]。 - 在x = 4处射出箭，击破气球[3,4]和[4,5]。提示:
1 <= points.length <= 105
points[i].length == 2
-231 <= xstart < xend <= 231 - 1
2 题目分析
输入是一个区间数组points，输出是一个整数ans，代表用最少几只箭可以射爆全部气球。射爆气球的条件是，其中
。
给的points是没有经过排序的，经过56合并区间和57插入区间，我们首先要对points进行排序。然后我们要分析箭射爆所有气球等价的操作，这部分在3.1模拟+贪心中详细讲述。
3 代码实现
3.1 模拟+贪心
首先先将points按左端点大小升序排序。我们注意到，用最少的弓箭射爆所有气球，实际上是贪心思想。已知要射爆气球的条件是，那我们要尽可能多射气球，就让x越靠进边界，即
或者
。这等价于当两个区间存在重合部分时，我们取它们较小的一个的右端点或者较大的一个左端点即可在这两个区间内。所以有如下算法流程图
时间复杂度O(n*log n)，空间复杂度O(log n)
C++代码实现
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
if(points.empty()){
return 0;
}
sort(points.begin(),points.end(), [](const vector<int>& u, const vector<int>& v){
return u[1]<v[1];
});
int arrow=points[0][1];
int ans=1;
for (const vector<int>& balloon: points) {
if (balloon[0] > arrow) {
arrow = balloon[1];
++ans;
}
}
return ans;
}
};Python代码实现
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
if not points:
return 0
points.sort(key=lambda x: x[1])
arrow = points[0][1]
ans = 1
for balloon in points:
if balloon[0] > arrow:
arrow = balloon[1]
ans += 1
return ans