用最少数量的箭引爆气球
在二维空间中有许多球形的气球。对于每个气球,提供的输入是水平方向上,气球直径的开始和结束坐标。由于它是水平的,所以纵坐标并不重要,因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。
一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭,若有一个气球的直径的开始和结束坐标为 xstart,xend, 且满足 xstart ≤ x ≤ xend,则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后,可以无限地前进。我们想找到使得所有气球全部被引爆,所需的弓箭的最小数量。
给你一个数组 points ,其中 points [i] = [xstart,xend] ,返回引爆所有气球所必须射出的最小弓箭数。
示例 1:
- 输入:points = [[10,16],[2,8],[1,6],[7,12]]
- 输出:2
- 解释:对于该样例,x = 6 可以射爆 [2,8],[1,6] 两个气球,以及 x = 11 射爆另外两个气球
示例 2:
- 输入:points = [[1,2],[3,4],[5,6],[7,8]]
- 输出:4
示例 3:
- 输入:points = [[1,2],[2,3],[3,4],[4,5]]
- 输出:2
示例 4:
- 输入:points = [[1,2]]
- 输出:1
示例 5:
- 输入:points = [[2,3],[2,3]]
- 输出:1
提示:
- 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]]
- 输出:3
如图所示,[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; } };
无重叠区间
给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。
注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”,但没有相互重叠。
示例 1:
- 输入: [ [1,2], [2,3], [3,4], [1,3] ]
- 输出: 1
- 解释: 移除 [1,3] 后,剩下的区间没有重叠。
示例 2:
- 输入: [ [1,2], [1,2], [1,2] ]
- 输出: 2
- 解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:
- 输入: [ [1,2], [2,3] ]
- 输出: 0
- 解释: 你不需要移除任何区间,因为它们已经是无重叠的了。
思路
做过射气球那题之后,这题就很好理解了
整体思路无非也是排序(左右边界均可,这里还是和上题保持一致,用左边界)后找出重叠区间,然后进行对应的处理
代码
和上题一样,没意思
步骤:
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; } };
总结
TBD