class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
}
};
452. 用最少数量的箭引爆气球
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 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原站题解
golang 解法, 执行用时: 216 ms, 内存消耗: 15.3 MB, 提交时间: 2023-05-29 17:38:32
func findMinArrowShots(points [][]int) int {
if len(points) == 0 {
return 0
}
sort.Slice(points, func(i, j int) bool { return points[i][1] < points[j][1] })
maxRight := points[0][1]
ans := 1
for _, p := range points {
if p[0] > maxRight {
maxRight = p[1]
ans++
}
}
return ans
}
javascript 解法, 执行用时: 288 ms, 内存消耗: 65.5 MB, 提交时间: 2023-05-29 17:38:18
/**
* @param {number[][]} points
* @return {number}
*/
var findMinArrowShots = function(points) {
if (!points.length ) {
return 0;
}
points.sort((a, b) => a[1] - b[1]);
let pos = points[0][1]
let ans = 1;
for (let balloon of points) {
if (balloon[0] > pos) {
pos = balloon[1];
ans++;
}
}
return ans;
};
python3 解法, 执行用时: 164 ms, 内存消耗: 49 MB, 提交时间: 2023-05-29 17:38:02
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
if not points:
return 0
points.sort(key=lambda balloon: balloon[1])
pos = points[0][1]
ans = 1
for balloon in points:
if balloon[0] > pos:
pos = balloon[1]
ans += 1
return ans
java 解法, 执行用时: 53 ms, 内存消耗: 74.6 MB, 提交时间: 2023-05-29 17:37:45
// 排序 + 贪心
class Solution {
public int findMinArrowShots(int[][] points) {
if (points.length == 0) {
return 0;
}
Arrays.sort(points, new Comparator<int[]>() {
public int compare(int[] point1, int[] point2) {
if (point1[1] > point2[1]) {
return 1;
} else if (point1[1] < point2[1]) {
return -1;
} else {
return 0;
}
}
});
int pos = points[0][1];
int ans = 1;
for (int[] balloon: points) {
if (balloon[0] > pos) {
pos = balloon[1];
++ans;
}
}
return ans;
}
}