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

目录

题目：

示例：

分析：

代码：

---

题目：

示例：

分析：

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

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

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

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

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

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

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

代码：

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