【LeetCode75】第七十三题 用最少数量的箭引爆气球

本文主要是介绍【LeetCode75】第七十三题 用最少数量的箭引爆气球，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

题目：

示例：

分析：

代码：

---

题目：

示例：

分析：

本题和上一题基本一样，上一题是要我们尽量让区间不重叠，而本题是要我们尽量让区间重叠。

所以我们的做法和上一题基本一致，只不过由于我们要让尽可能多的区间重叠才可以用最少的箭来引爆所有气球。

因此我们一样是对区间进行排序，按照 左端从小到大的顺序。

接着是拿一个变量去接收最小的右端。

不过右端的更新情况跟上一题相比有点不同。我们在遇到不重叠的区间的时候，所需用的箭+1，并且直接将右端点更新成新的区间的右端点。

在遇到重叠区间的时候我们就将右端点更新为较小值。

并且跟上一题不一样的是，我们起码要用一根箭，所以答案初始化为1。

代码：

class Solution {
public:int findMinArrowShots(vector<vector<int>>& points) {//以左端点为升序排序.sort(points.begin(),points.end(),[&](vector<int> &a,vector<int> &b){return a[0]<b[0];});int res=1;int end=points[0][1]; //记录最小的右端点for(int i=1;i<points.size();i++){if(points[i][0]<=end){end=min(end,points[i][1]);}else{end=points[i][1];res++;}}return res;}
};

这篇关于【LeetCode75】第七十三题 用最少数量的箭引爆气球的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---