C ++中爆破气球的最小箭头数

假设在二维空间中散布的球形气球很少。对于每个气球，都有水平直径的起点和终点坐标。开始总是小于结束。最多会有104个气球。可以从沿x轴的不同点垂直垂直向上射出一个箭头。如果xstart = x = xend，则位置为xstart到xend的气球会通过向x方向射击的箭头爆炸。可以拍摄的箭头数量没有限制。假设一次射出的箭头不断向上移动。我们必须找到爆破所有气球所必须射出的最少箭头数。因此，如果输入像[[10,16]，[2,8]，[1,6]，[7,12]]，则输出将为2。因此，如果我们从x = 6拍摄，会爆裂[2,8]和[1,6]，并且另一个x = 11的气球会爆裂其余部分。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个方法intersect()来检查位置是否相交

• manipulate()取完所有相交气球的范围后另一种操纵范围的方法

• 实际方法是将气球位置设为pos

• 根据结束位置对pos数组排序

• n：=气球数量，如果n为0，则返回0

• currEnd：=定位后pos的第一个条目的结束位置

• 中位数：= 1

• 当我在1到n – 1的范围内时

• 如果currEnd <pos [i]的开始位置，则将计数增加1，并且currEnd：= pos [i]的结束位置

• 返回计数

让我们看一下下面的实现以获得更好的理解

示例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool intersect(vector <int>& a, vector <int>& b){
      return a[1] >= b[0];
   }
   static bool cmp(vector <int>& a, vector <int>& b){
      return a[1] < b[1];
   }
   void manipulate(vector <int>& a, vector <int>& b){
      a[0] = min(a[0], b[0]);
      a[1] = max(a[1], b[1]);
   }
   int findMinArrowShots(vector<vector<int>>& points) {
      sort(points.begin(), points.end(), cmp);
      int n = points.size();
      if(!n) return 0;
      int currEnd = points[0][1];
      int cnt = 1;
      for(int i = 1; i < n; i++){
         if(currEnd < points[i][0]){
            cnt++;
            currEnd = points[i][1];
         }
      }
      return cnt;
   }
};
main(){
   vector<vector<int>> v = {{10,16},{2,8},{1,6},{7,12}};
   Solution ob;
   cout << (ob.findMinArrowShots(v));
}

输入值

[[10,16],[2,8],[1,6],[7,12]]

输出结果

2