刷题笔记Day30贪心算法part04

刷题笔记Day30：贪心算法part04

题目：用最少数量的箭引爆气球

452. 用最少数量的箭引爆气球 - 力扣（LeetCode）
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 x``start，x``end， 且满足  xstart ≤ x ≤ x``end，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。
给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。
示例 1：

1. 输入：points = [[10,16],[2,8],[1,6],[7,12]]
2. 输出：2
3. 解释：气球可以用2支箭来爆破:
4. -在x = 6处射出箭，击破气球[2,8]和[1,6]。
5. -在x = 11处发射箭，击破气球[10,16]和[7,12]。

复制代码

思路：是一个重叠问题，因此需要先对points做一个排序结果为[[1,6],[2,8],[7,12],[10,16]]，经过排序后我们要对比的方式是此刻气球的开始位置和上一个气球的结束位置是否有重叠，若有重叠说明可以一次打爆两个气球，例如第一个和第二个，但是如何判断第三个或者以后的气球是否在第一支箭矢的，因此在第一次判断后若能使用一支箭射爆两个气球后，需要判断第一个气球的末尾位置和第二个气球的末尾位置哪个位置较小，将较小的值赋给第二个气球的末尾，一次类推。代码：
[code]class Solution {public:    static bool cmp(const vector& a, const vector& b){        if(a[0] == b[0])    return a[1]