39 lines
1.4 KiB
JavaScript
39 lines
1.4 KiB
JavaScript
/**
|
||
* https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/?envType=study-plan-v2&envId=top-interview-150
|
||
* @param {number[][]} points
|
||
* @return {number}
|
||
*/
|
||
const findMinArrowShots = function (points) {
|
||
|
||
};
|
||
|
||
/*
|
||
将points按照start排序，从第一个point开始遍历，所射箭的位置取第一个point的end，之后查看第二个point，
|
||
如果第二个point的end比第一个point的end小就把箭的x坐标移动到第二个point的end，这样就能保证之前气球
|
||
引爆的情况下也能引爆当前气球，可以做到箭的作用的最大化，如果之前最小的end比当前point还小，则表明需要，
|
||
新增一直箭
|
||
*/
|
||
|
||
function f1(points) {
|
||
if (points.length === 0) return 0;
|
||
|
||
// 按照气球的左边界进行排序
|
||
points.sort((a, b) => a[0] - b[0]);
|
||
|
||
let arrows = 1; // 初始化箭的数量
|
||
let arrowX = points[0][1]; // 第一个箭的位置是第一个气球的右边界
|
||
|
||
for (let i = 1; i < points.length; i++) {
|
||
// 如果当前气球的左边界大于箭的位置，说明需要新的箭
|
||
if (arrowX < points[i][0]) {
|
||
arrows++; // 增加箭
|
||
arrowX = points[i][1]; // 更新箭的位置为当前气球的右边界
|
||
} else {
|
||
// 否则，箭可以继续覆盖当前气球，更新箭的位置为当前气球的右边界（确保尽量覆盖更多气球）
|
||
arrowX = Math.min(arrowX, points[i][1]);
|
||
}
|
||
}
|
||
|
||
return arrows;
|
||
}
|