leetcode 第452题
时间: 2023-09-14 19:14:59 浏览: 215
LeetCode题目解答
LeetCode第452题是「用最少数量的箭引爆气球」(Minimum Number of Arrows to Burst Balloons),是一道贪心算法的题目。
题目描述:
在一个二维空间中,给定许多气球,每个气球的直径都不同,而且不同气球之间可能会有重叠的部分。如果一支弓箭能够穿过某个气球,那么就算这支弓箭是有效的。而且为了使得弓箭的使用次数最少,你可以假设每个气球被射爆的位置都是相同的。请问至少需要多少支弓箭才能将所有气球射爆?
示例:
输入:[[10,16],[2,8],[1,6],[7,12]]
输出:2
解释:
对于输入的气球,我们可以在 x = 6(射爆气球 [2,8],[1,6])和 x = 11(射爆气球 [10,16],[7,12])处各用一支箭。
提示:
1. 气球数量不大于 10^4。
2. 气球的坐标系数值均在范围 [-10^6, 10^6] 内。
3. Interval(区间)类用来表示区间,例如列表中的气球坐标表示为 [start, end]。
具体思路可以参考题解区的解答。
阅读全文