【LeetCode贪心#09】用最少数量的箭引爆气球，（涉及区间重叠情况判断） - dayceng

用最少数量的箭引爆气球

力扣题目链接(opens new window)

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

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

给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。

• 输入：points = [[10,16],[2,8],[1,6],[7,12]]
• 解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球

• 输入：points = [[1,2],[3,4],[5,6],[7,8]]

• 输入：points = [[1,2],[2,3],[3,4],[4,5]]

• 输入：points = [[1,2]]

• 输入：points = [[2,3],[2,3]]

• 0 <= points.length <= 10^4
• points[i].length == 2
• -2^31 <= xstart < xend <= 2^31 - 1

题干描述套了一个“打气球”作为背景，搞得有点抽象，其实就是给一个二维数组，寻找里面子数组的重合区间的一个问题

题意图解如下：

• 输入：points = [[1,2],[3,6],[4,8],[7,12],[10,16]]

如图所示，[1,2]和[3,6]两个区间所代表的的“气球”没有重合，因此不能同时打爆

而[3,6]和[4,8]位置的两个“气球”是有重合的，因此可以使用一支箭同时打爆

同理[7,12]和[10,16]位置也可以消耗一支箭打爆两个气球，因此要打爆所有气球，最少使用的箭数是3

你可能会想：那为什么不能同时打爆[4,8]和[7,12]位置的气球呢？

如果是上面这种打法，那不重叠的[3,6]和[10,16]区间又分别需要消耗两支箭，导致整体使用箭数不是最少

因此同时打爆[4,8]和[7,12]位置的气球不是最优解

由上述讨论可以得出贪心思路：

局部最优：让重叠区间尽可能多的在一块，好一次打完

全局最优：使用最少的箭打完所有气球

本题难点有两个：

1、如何模拟射气球的过程

2、如何记录重叠数组

模拟射气球时，不需要真的去删除被射中的气球数组，只需计数即可

还是以上面的图为例

先将所有气球按照左边界排序

情况1：不重叠，需要额外使用箭

以[1,2]和[3,6]为例，[3,6]的左边界3大于[1,2]的右边界2，因此这两个区间无重叠，需要两支箭分别射击，即：

if(points[i][0] > points[i - 1][1]){//左边界3大于右边界2
    res++;//使用弓箭数增加	
}

情况2：重叠检查并更新右边界

以[3,6]和[4,8]为例，显然这两个位置的气球时重叠的，那肯定就不满足情况1的条件，因此我们可以接着情况1写在else里面

if(points[i][0] > points[i - 1][1]){//左边界3大于右边界2
    res++;//使用弓箭数增加	
}else{//(points[i][0] <= points[i - 1][1]的情况
    
}

为什么有等于？因为题目说了挨着的气球也可以一次打爆

当气球有重合时，我们不需要使用新的弓箭。但是如果遍历到下一个区间，它也与之前的区间有重合，我们怎么去处理这种情况？

这个时候就需要在遇到重叠区间时，记录当前最小的右边界以提供给下一个区间进行重叠判断

如图所示，当下标i遍历到[4,8]区间时，其与下标为i - 1的[3,6]区间有重合

此时不知道之后会不会还有区间与这两个区间有重合，所以需要记录下这两个区间中最小的那个右边界用于后续判断

最小右边界显然是6，当下标i遍历到[7,12]时，[7,12]的左边界大于当前的最小右边界6

所以[7,12]没有与[3,6]、[4,8]有重叠部分，因此需要额外的弓箭来射击（满足情况1）

所以情况2的代码逻辑如下：

if(points[i][0] > points[i - 1][1]){//左边界3大于右边界2
    res++;//使用弓箭数增加	
}else{//(points[i][0] <= points[i - 1][1]的情况
    points[i][1] = min(points[i - 1][1], points[i][1]);//取两个重合区间中最小的右边界作为当前右边界
}

根据上述分析可以总结出以下步骤：

1、自定义比较规则cmp，按左边界对数组先进行排序

2、判断数组为0的情况

2、初始化弓箭数量变量（注意初始值为1，因为0的情况已经判断过，所以之后的情况至少需要一支弓箭）

3、遍历数组，判断两种情况

• 情况1，无重叠，更新res值记录所需的新弓箭
• 情况2，有重叠，更新最小右边界，即(points[i] [0] <= points[i - 1] [1]

class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b){
        return a[0] < b[0];
    }
    int findMinArrowShots(vector<vector<int>>& points) {
        if (points.size() == 0) return 0;//先判断数组为0的情况
        //对二维数组进行排序
        sort(points.begin(), points.end(),cmp);
        int res = 1;//记录弓箭使用数量，因为0的情况已经判断过，所以之后的情况至少需要一支弓箭
        //遍历数组
        for(int i = 1; i < points.size(); ++i){//从1开始，不然比到最后会有负数
            //判断左右边界情况，即重叠情况
            if(points[i][0] > points[i - 1][1]){//情况1，无重叠
                res++;
            }else{//情况2，有重叠，更新最小右边界//(points[i][0] <= points[i - 1][1]
                points[i][1] = min(points[i - 1][1], points[i][1]);
            }
        }
        return res;
    }
};

无重叠区间

力扣题目链接(opens new window)

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

• 输入: [ [1,2], [2,3], [3,4], [1,3] ]
• 解释: 移除 [1,3] 后，剩下的区间没有重叠。

• 输入: [ [1,2], [1,2], [1,2] ]
• 解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

• 输入: [ [1,2], [2,3] ]
• 解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

做过射气球那题之后，这题就很好理解了

整体思路无非也是排序（左右边界均可，这里还是和上题保持一致，用左边界）后找出重叠区间，然后进行对应的处理

和上题一样，没意思

1、自定义排序

2、定义变量记录需要删除的区间的个数

3、遍历区间，判断重叠情况

• 左边界大于等于右边界（区别于上一题，本题相邻的情况也算作不重叠），无重叠，不进行任何操作
• 左边界小于右边界，区间重叠，当前区间为待删除区间，更新删除区间的数量

class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b){
        return a[0] < b[0];
    } 
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        //排序
        sort(intervals.begin(), intervals.end(), cmp);
        int removeNums = 0;//记录移除区间数量，从1开始
        //遍历
        for(int i = 1; i < intervals.size(); ++i){
            if(intervals[i][0] >= intervals[i - 1][1]){//不重叠，无操作

            }else{//区间重叠
                intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]);//更新当前重叠区间中的最细小右边界的
                removeNums++;//记录需要移除的区间
            }
        }
        return removeNums;
    }
};