leetcode：452. 用最少数量的箭引爆气球_算法最少箭引爆气球

题目来源

• minimum-number-of-arrows-to-burst-balloons

题目描述

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {

    }
};
1
2
3
4
5
6

题目解析

问题：要求当前位置下(不许排序)，要把所有的箭头引爆，需要使用多少箭

• 遍历所有数组，从第一个气球开始，如果可以引爆其他气球，就引爆他们
• 因为对于当前最小的区间来说，无论我按照什么顺序去射，早晚都需要引爆它
• 但是我们要弓箭最小，应该怎么排列，怎么设计才能最少
  • 对于单独的一个气球，我们至少需要使用一次弓箭
  • 对于多个气球，我们在进行射击时，可以尽可能多的再射击到其他气球
  • 一支箭射穿多个区间，它们都是有重合的。我们应该尽量把有重合的区间堆在一起，给上一箭。

为了方便在一次遍历中识别重合，先进行排序，是按照区间左端还是右端升序呢？

其实都可以，但是建议按照右端点进行排序：

• 如果按左端升序排序：
  • 有交集关系的区间中，有的区间结束位置比较早
  • 第一箭的位置需要进行迭代判断，取区间 [0, 6]、[1, 2] 中结束位置最小的位置，即 arrow_pos = min(points[i][1], arrow_pos)，然后再判断接下来的区间是否能够引爆。

[0..................6]
   [1..2]    
             [4..5]
1
2
3

         Λ
  [-------|]
     [----|------] //这俩哥们一个箭够了
        [-|---------] //如果第三个是这样的，那一根箭还是够的
          |  [-------]  //如果是这样的呢，不行了，因为这个的start小于第一行那个end了，所以得再加一根
1
2
3
4
5

• 如果对右端点进行排序：
  • 箭的位置一开始就确定了，不需要再改变和判断箭的位置，直接判断区间即可。

       Λ  
  [-----|]     
[-------|---]  
  [-----|---]
     [--|---]
        |  [-----]  // 只有此时需要再来一根

1
2
3
4
5
6
7

我们来分析下按照**左端点(起始位置)**进行排序的过程

问题：从前向后遍历遇到重叠的气球了怎么办？

举个例子，假设我们已经对气球排序了，而且得到了[1, 6]，[2, 8]，[7, 12]，[9, 10]。

我们对这四个气球进行遍历

• 当我们遍历到第一个气球时，可以获得一个射击区间$[1,6]$，这这个区间里，一定可以射中第一个气球
  
• 当我们遍历到第二个气球时，由于第二个区间的左端点小于射击区间的右边界，而右端点大于射击区间的左边界，因此我们重新确立射击区间[2, 6]

• 当我们遍历到第三个气球时，其左端点大于射击区间的右边界，因此我们在原先的射击区间中是无法打中第三个气球的，我们需要重新开辟一块射击区间 [7, 12]。

• 当我们遍历到第四个气球时，其左端点小于射击区间的右边界，右端点也小于射击区间的右边界，因此需要缩小射击区间。

• 至此，我们至少需要两次射击才能引爆气球。

在以上的分析中，我们事实上是不需要考虑射击区间的左边界的，因为我们已经对气球进行了排序，所以每次的区间确定，左区间总是要改变的。我们核心要考虑的是右区间和新遍历的气球的左右两个端点的关系：

• 如果新气球的左端点大于射击区间的右边界，那么我们就需要开辟一个新的区间（新的箭）
• 如果新气球的左端点小于射击区间的右边界，这里又要分为两种情况：
  • 如果右端点大于射击区间的右边界，那么我们的射击区间的右边界无需变化；
  • 如果右端点小于射击区间的右边界，那么我们射击区间的右边界就要向左移动，以新气球的右端点为准，确立新的边界。

代码实现：

• 先根据start进行升序排序，然后从索引1开始遍历数组，比较当前下标i位置的左坐标points[i][0]和前一个右坐标points[i-1][1]的大小关系
  • 如果points[i]-1[1] < points[i+1][0]，说明不重叠，此时需要一支新的箭
  • 如果points[i-1][1] >= points[i][0]，说明有重叠区间，此时我们需要更新当前气球的右坐标用来标记重合区间的右坐标，方便接下来对比时判断是否重合，即points[i][1] = min(points[i][1] , points[i-1][1])

class Solution {
private:
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    }
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if (points.size() == 0) return 0;
        sort(points.begin(), points.end(), cmp);

        int result = 1; // points 不为空至少需要一支箭
        for (int i = 1; i < points.size(); i++) {
            if (points[i][0] > points[i - 1][1]) {  // 气球i和气球i-1不挨着，注意这里不是>=
                result++; // 需要一支箭
            }
            else {  // 气球i和气球i-1挨着
                points[i][1] = min(points[i - 1][1], points[i][1]); // 更新重叠气球最小右边界
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

按照end进行排序

步骤：

• 前面的气球必须要消耗掉
• 射未爆第一个气球的尾部
• 消耗掉此次射击连带的气球，算法实现上就是跳过这个气球
• 箭头再次指向未爆第一个气球的尾部

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 pos = points[0][1];
        int ans = 1;
        for (const vector<int>& balloon: points) {
            if (balloon[0] > pos) {  // 开始区间 > 末尾区间，说明不挨着了
                pos = balloon[1];  //因为是按照末尾排序的
                ++ans;
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

思路

弓箭的起始位置和结束位置可以看做是一段区间，直观上来看，为了使用最少的弓箭数，可以尽量射中区间重叠最多的地方。

所以问题变为了：如何寻找区间重叠最多的地方，也就是区间交集最多的地方。

区间调度问题：给定一些有交集的区间，形如[[start1, end1],[start2,end2],…]，求最大不相交的区间数量。

对于此题，如果最多有n个不相交的区间，则需要的箭至少为n个。

对区间调度问题，先按各区间的end升序排序，再从前向后遍历区间，对比后面区间的start和前面区间的end，检查是否有交集。

【动态规划+图解思路】
参考
参考