排序 + 贪心
- 思路：
- 将数组元素按照右边界进行排序；
- 第一支箭从第一个气球的右边界 pos 射出，如果下一个气球的左边界比 pos 要大，则这个气球不会被这支箭射中，否则会被射中（因为排过序 pos ∈ [left, right]）；
- 如果射不中，需要下一支箭，同时将 pos 更新为这个气球的 right；
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
if (points.empty()) {
return 0;
}
std::sort(points.begin(), points.end(), [](const std::vector<int>& u, const std::vector<int>& v) {
return u[1] < v[1];
});
int pos = points[0][1];
int count = 1;
for (const vector<int>& q: points) {
if (q[0] > pos) {
pos = q[1];
++count;
}
}
return count;
}
};文章来源地址https://www.toymoban.com/news/detail-808566.html
文章来源：https://www.toymoban.com/news/detail-808566.html
到了这里，关于力扣452. 用最少数量的箭引爆气球的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
