本文主要是介绍【leetcode题解C++】452.用最少数量的弓箭引爆气球 and 435.无重叠区间，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
452. 用最少数量的弓箭引爆气球
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。
给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。
示例 1：
输入：points = [[10,16],[2,8],[1,6],[7,12]] 输出：2 解释：气球可以用2支箭来爆破: -在x = 6处射出箭，击破气球[2,8]和[1,6]。 -在x = 11处发射箭，击破气球[10,16]和[7,12]。
示例 2：
输入：points = [[1,2],[3,4],[5,6],[7,8]] 输出：4 解释：每个气球需要射出一支箭，总共需要4支箭。
示例 3：
输入：points = [[1,2],[2,3],[3,4],[4,5]] 输出：2 解释：气球可以用2支箭来爆破: - 在x = 2处发射箭，击破气球[1,2]和[2,3]。 - 在x = 4处射出箭，击破气球[3,4]和[4,5]。
思路：看到这种情况，要想通过遍历来判断能否“一箭多雕”，那么肯定需要排序的，这个排序规则需要自定义，按气球起始的x，从小到大排序，然后进行判断。通过一个气球结束的x来和下一个气球起始的x比较，判断能否一箭引爆前后两个气球（既然能引爆，“气放光”也没关系），然后为了确保箭射入的位置能完成这个动作，可以将第二个气球“放气”，让第二个气球结束的x变为第一个气球结束的x。（需要注意的是，题目中给出过至少会有一个气球，所以不用判断气球数为0的情况）
代码实现：
class Solution {
public:static bool mySort(const vector<int> &a, const vector<int> &b) {return a[0] < b[0];}int findMinArrowShots(vector<vector<int>>& points) {sort(points.begin(), points.end(), mySort);int ret = 1; //题目说了至少会有一个气球for(int i = 0; i < points.size() - 1; ++i) {if(points[i][1] < points[i + 1][0]) {++ret;}else { //限定范围，保证一支箭击破前后两个气球points[i + 1][1] = min(points[i + 1][1], points[i][1]);}}return ret; }
};435. 无重叠区间
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
示例 1:
输入: intervals = [[1,2],[2,3],[3,4],[1,3]] 输出: 1 解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2:
输入: intervals = [ [1,2], [1,2], [1,2] ] 输出: 2 解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:
输入: intervals = [ [1,2], [2,3] ] 输出: 0 解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
思路：和上面一题有些相似，不过这里要怎么排序呢？——因为要判断的是前者的右边界是否在后者的范围内，那么，按右边界排序。遍历比较的过程和上面都是大同小异的。记得在合适的情况更新边界。
代码实现：
class Solution {
public:static bool mySort(const vector<int> &a, const vector<int> &b) {return a[1] < b[1]; //按右边界从小到大排序，因为要判断的是前者的右边界有没有在在后者的范围内}int eraseOverlapIntervals(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end(), mySort);int ret = 0;int end = intervals[0][1]; //记录起始的右边界for(int i = 1; i < intervals.size(); ++i) {if(end > intervals[i][0]) { //重叠++ret;}else if(end <= intervals[i][0]) { //不重叠end = intervals[i][1];}}return ret;}
};这篇关于【leetcode题解C++】452.用最少数量的弓箭引爆气球 and 435.无重叠区间的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
