Leetcode 452

这道题最初没有想出来,看了题解恍然大悟。右边界升序排列是问题的关键。

题目

原题链接:
https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons/

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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

----本文结束啦感谢您阅读----

欢迎关注我的其它发布渠道