138、【贪心算法】leetcode ——452. 用最少数量的箭引爆气球(贪心区间重叠问题)(C++版本)
2023-09-11 14:20:01 时间
题目描述
原题链接:452. 用最少数量的箭引爆气球
解题思路
局部最优解: 气球出现重叠时,在重叠区域射一箭,以此方式射完所有气球
全局最优解: 所有气球射完,所用弓箭最少。
先按气球左边界从大到小排列。每次对比前后两个区间,当区间不重叠时,需要用到一个弓箭,弓箭数加一。当出现重叠时,更新此时允许发射范围的边界,更新第二个气球的右区间,取重叠边界。
class Solution {
public:
static bool cmp(const vector<int>& a, const vector<int> & b) {
return a[0] < b[0];
}
int findMinArrowShots(vector<vector<int>>& points) {
sort(points.begin(), points.end(), cmp); // 按从小到大排序
int res = 1; // 仅有一个时,也需要一个
for(int i = 1; i < points.size(); i++) {
if(points[i - 1][1] < points[i][0]) { // 第二个气球的左边界与第一个气球的右边界重叠
res++;
}
else {
points[i][1] = min(points[i - 1][1], points[i][1]); // 右边界,取满足两者重叠的边界
}
}
return res;
}
};
相关文章
- C++构造函数实例——拷贝构造,赋值
- 基于OpenCV的灰度图像归一化到0~255(即对比度拉伸)的C++代码,并附原理介绍
- 《Visual C++ 开发从入门到精通》——第2章 C++的基本语法2.1 面向对象
- 《C和C++代码精粹》——2.12 指向函数的指针
- 纪念逝去的岁月——C++实现一个栈(使用类模板)
- 203、【栈与队列】leetcode ——剑指 Offer II 040. 矩阵中最大的矩形 / 85. 最大矩形:暴力+单调栈(C++/Pyhont版本)
- 200、【数组】leetcode ——6316. 重排数组以得到最大前缀分数(C++版本)
- 189、【动态规划】leetcode ——312. 戳气球(C++版本)
- 174、【动态规划/贪心算法/滑动窗口】leetcode ——674. 最长连续递增序列:一题多解 (C++版本)
- 160、【动态规划】leetcode ——279. 完全平方数:二维数组+一维滚动数组(C++版本)
- 141、【贪心算法】leetcode ——56. 合并区间(区间重叠解法+双指针解法)(C++版本)
- 139、【贪心算法】leetcode ——435. 无重叠区间(更新区间+记录不重叠区间)(C++版本)
- 130、【贪心算法/动态规划】leetcode ——122. 买卖股票的最佳时机 II(C++版本)
- 126、【回溯算法】leetcode ——332. 重新安排行程:回溯算法(C++版本)
- 125、【回溯算法】leetcode ——47.全排列 II:visited去重(C++版本)
- 114、【回溯算法】leetcode ——77. 组合:回溯法+剪枝优化(C++版本)
- 108、【树与二叉树】leetcode ——235. 二叉搜索树的最近公共祖先:普通树解法+BST性质解法(C++版本)
- 97、【树与二叉树】leetcode ——513.找树左下角的值:层次遍历+回溯法(C++版本)
- 93、【树与二叉树】leetcode ——222. 完全二叉树的节点个数:普通二叉树求法+完全二叉树性质求法(C++版本)
- 92、【树与二叉树】leetcode ——111. 二叉树的最小深度:层次遍历+先序DFS+后序DFS[子问题分解](C++版本)
- 80、【字符串】leetcode ——459. 重复的子字符串(C++版本)
- 79、【字符串】leetcode ——28. 找出字符串中第一个匹配项的下标(C++版本)
- 68、【哈希表】leetcode——349. 两个数组的交集(C++版本)
- 62、【数组】leetcode——54. 螺旋矩阵:N*M型(C++版本)
- 60、【数组】leetcode——904. 水果成篮-滑动窗口:最大窗口(C++版本)
- C++11时间具体解释
- C和C++内存分配方式记录