452. 用最少数量的箭引爆气球 - 力扣LeetCode452. 用最少数量的箭引爆气球 - 有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points 其中points[i] [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭若有一个气球的直径的开始和结束坐标为 xstartxend 且满足 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]。 提示: * 1 points.length 105 * points[i].length 2 * -231 xstart xend 231 - 1https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/题目描述有一些球形气球贴在一堵用 XY 平面表示的墙面上。气球数组points其中points[i] [xstart, xend]表示气球的水平直径的起始和终止坐标。 一支弓箭可以沿着 x 轴从不同点垂直射出。如果箭的位置x满足xstart ≤ x ≤ xend气球会被引爆。 求引爆所有气球最少需要多少支箭。核心区间贪心经典题和区间合并思路接近但有区别只要区间有交集同一支箭就能一起射爆箭要放在重叠区间最靠右的边界。解法先对数组进行排序,从小到大依靠贪心,我们这里需要找到重叠的区间,使之包含的所在区间的气球个数最多,如果不在上一段的重合区间就要将区间重新进行跟新,变成当前比较区间的最右侧.class Solution { public: int findMinArrowShots(vectorvectorint points) { sort(points.begin(),points.end()); // 找重合 int rightpoints[0][1]; int leftpoints[0][0]; int npoints.size(); int ret0; for(int i1;in;i) { int apoints[i][0]; int bpoints[i][1]; if(aright) { rightmin(b,right); } else { ret; rightb; } } return ret1; } };