北京电子商务网站建设,建设银行网站首页下载,做的好的家装网站,如何制作个人公众号452. 用最少数量的箭引爆气球452. 用最少数量的箭引爆气球 有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points #xff0c;其中points[i] [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可…452. 用最少数量的箭引爆气球452. 用最少数量的箭引爆气球 有一些球形气球贴在一堵用 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 105points[i].length 2-231 xstart xend 231 - 1 class Solution {static bool cmp(vectorint a,vectorint b){return a[0]b[0];}
public:int findMinArrowShots(vectorvectorint points) {int npoints.size();//排序sort(points.begin(),points.end(),cmp);//箭数初始化为1if(n0){return 0;}int ans1;for(int i1;in;i){//下一个气球的左边界小于上一个气球的右边界就要再加一支箭if(points[i][0]points[i-1][1]){ans;}else{points[i][1]min(points[i][1],points[i-1][1]);}}return ans;}
};
