452. 用最少数量的箭引爆气球
贪心算法
思路
首先对数组按照右边界升序排序。我们从第一个气球的右边界开始射箭，寻找气球左边界小于第一个气球右边界的气球（因为这些气球一定会被同时引爆），而当遍历到某个气球的最左侧值大于当前射出的箭最右侧值的时候，我们之前射出的箭并不能解决掉这个气球，这时候就需要一支新的箭在这个不能解决掉的气球的最右侧发射。在这样的贪心策略下（由局部最优（如果当前射出最右侧的箭都不能解决某个气球，才需要一支新的箭）找到全局最优），最终会得到最少的箭数。
代码分析
class Solution { public: static bool cmp(vector<int> &a, vector<int> &b) { return a[1] < b[1]; } int findMinArrowShots(vector<vector<int>> &points) { sort(points.begin(), points.end(), cmp); int pre = points[0][1], count = 1; for (int i = 1; i < points.size(); i++) { // 无重叠则开启下一轮 if (points[i][0] > pre) { pre = points[i][1]; count++; } } return count; } };
主要是参考了之前无重叠区间的思想，改写了一下，还是比较顺利的。
复杂度分析
时间复杂度：O ( n l o g n )，其中 n nn 是数组 p o i n t s 的长度。排序的时间复杂度为 O ( n l o g n ) ，对所有气球进行遍历并计算答案的时间复杂度为 O ( n )，其在渐进意义下小于前者，因此可以忽略。
空间复杂度：O ( l o g n ) ，即为排序需要使用的栈空间。
