网站规划建设与管理维护教程与实训,北京建设银行网站,wordpress去category,家电维修 做网站还是搞公众号在二维空间中有许多球形的气球。对于每个气球#xff0c;提供的输入是水平方向上#xff0c;气球直径的开始和结束坐标。由于它是水平的#xff0c;所以y坐标并不重要#xff0c;因此只要知道开始和结束的x坐标就足够了。开始坐标总是小于结束坐标。平面内最多存在104个气球…在二维空间中有许多球形的气球。对于每个气球提供的输入是水平方向上气球直径的开始和结束坐标。由于它是水平的所以y坐标并不重要因此只要知道开始和结束的x坐标就足够了。开始坐标总是小于结束坐标。平面内最多存在104个气球。
一支弓箭可以沿着x轴从不同点完全垂直地射出。在坐标x处射出一支箭若有一个气球的直径的开始和结束坐标为 xstartxend 且满足 xstart ≤ x ≤ xend则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后可以无限地前进。我们想找到使得所有气球全部被引爆所需的弓箭的最小数量。
Example:
输入:
[[10,16], [2,8], [1,6], [7,12]]输出:
2解释: 对于该样例我们可以在x 6射爆[2,8],[1,6]两个气球和 x 11射爆另外两个气球。
class Solution {
public:int findMinArrowShots(vectorvectorint points) {if (points.size() 0) {return 0;}sort(points.begin(), points.end(), [](const vectorint v1, const vectorint v2) {return v1[1] v2[1];});int res 0;int end;int i 0;while (ipoints.size()) {res ;end points[i][1];i;while (i points.size() end points[i][0] end points[i][1]) {i;}}return res;}
};来源力扣LeetCode
