贪心：Burst Balloons 最少次数完成射击气球

首页 > 贪心：Burst Balloons 最少次数完成射击气球

贪心：Burst Balloons 最少次数完成射击气球

已知在一个平面上有一定数量的气球，平面可以看作一个坐标系，在平面的x轴的不同位置安排弓箭手向y轴方向射箭，弓箭可以向y轴走无穷远;给定气球的宽度 xstart ≤ x ≤ xend，问至少需要多少弓箭手，将全部气球打爆?

例如: 四个气球 : [[10,16], [2,8], [1,6], [7,12]]，至少需要2个弓箭手。

如下过程

在这里插入图片描述

在射击的过程中想要安排最少的弓箭手保证能够完成所有气球的射击任务，我们可以从中寻找到贪心规律

对于一个气球，至少需要一个弓箭手才能够射穿
当一个弓箭手射穿一个气球的同时尽可能多得射穿其他的气球，这就是我们想要达到的安排最少弓箭手的方式

可以使用如下迭代策略：

维护一个射击区间，保证在遍历气球的过程中射击区间的左端点是小于右端点；否则就需要增加一个弓箭手，同时再维护一个新的射击区间。

算法实现如下:

/*
贪心规律：
维护一个射击区间，且该射击区间不断缩小，直到容纳最多的气球
*/
int get_least_shooter(vector<pair<int,int>> &bollon) { if (bollon.size() < 2) { return bollon.size();}int shooter = 1;/*排序的目的是为了保证气球的起始值从小到大，随着遍历的进行，气球的起始值逐渐增大*/sort(bollon.begin(),bollon.end(),cmp);int begin = bollon[0].first;//射击区间的左边界int end = bollon[0].second;//射击区间的右边界for (int i = 0;i < bollon.size(); ++i) { if (end >= bollon[i].first) {  //当左边界大于右边界时停止维护射击区间begin = bollon[i].first;if (end > bollon[i].second) { //不断缩小右边界的范围end = bollon[i].second;}} else{ shooter++;begin = bollon[i].first;end = bollon[i].second;}}return shooter;
}

测试代码如下:

#include 
#include 
#include using namespace std;bool cmp(pair<int,int> a,pair<int,int> b) { return a.first < b.first;
}int get_least_shooter(vector<pair<int,int>> &bollon) { if (bollon.size() < 2) { return bollon.size();}int shooter = 1;sort(bollon.begin(),bollon.end(),cmp);int begin = bollon[0].first;int end = bollon[0].second;for (int i = 0;i < bollon.size(); ++i) { if (end >= bollon[i].first) { begin = bollon[i].first;if (end > bollon[i].second) { end = bollon[i].second;}} else{ shooter++;begin = bollon[i].first;end = bollon[i].second;}}return shooter;
}int main(){ vector<pair<int,int>> bollon;pair<int,int> a;cout <<"constuct the bollon " << endl;for (int i = 0;i < 5; ++i) { cin >> a.first;cin >> a.second;bollon.push_back(a);}cout << "the least of the shootors is " << get_least_shooter(bollon);return 0;
}

输出结果如下

constuct the bollon 
10 16
2 8
1 6
7 12
20 21
the least of the shootors is 3

贪心：Burst Balloons 最少次数完成射击气球

更多相关：

java 读取excel_Java12POI操作Excel

C++ 生成随机数

基于C++的本征图像分解(Intrinsic Image Decomposition)

剑指offer：面试题39. 数组中出现次数超过一半的数字

剑指offer：面试题33. 二叉搜索树的后序遍历序列

leetcode-452 用最少数量的箭引爆气球