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