LC 0452 [M] Minimum Number of Arrows to Burst Balloons - ALawliet/algorithms GitHub Wiki
In a word, it doesn't matter where we shoot. As a greedy problem, the guideline here is that we can shoot as many balloons as possible when we shoot the current balloon. Shooting at the end or the start is decided by how we sort the array. And if we don't do the sorting, it's not guaranteed to start from the leftmost/rightmost balloon, which dangers our sub-optimal assumption.
It's symmetric. Since you sort the array in descending order you would want to shoot at their left-edges. IF you instead sort in ascending order you'd want to shoot at the right edges. You can just check the case of 2 balloons with two cases: overlapping or not, to see why.
greedy overlapping intervals problem but we sort by end instead of start because we want to shoot as many possible instead of use as few meeting rooms
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
points = sorted(points, key=lambda x: x[1]) # sort by end
shot = float('-inf')
ans = 0
# shoot rightmost
for p in points:
if p[0] <= shot <= p[1]:
continue
else:
ans += 1
shot = p[1] # last end shot
return ans
sort by end
class Solution(object):
def findMinArrowShots(self, points):
"""
:type points: List[List[int]]
:rtype: int
"""
points = sorted(points, key = lambda x: x[1])
res, end = 0, -float('inf')
for interval in points:
if interval[0] > end:
res += 1
end = interval[1]
return res
sort by start
def findMinArrowShots(self, points):
ret, shoot = 0, float('inf')
for s, e in sorted(points, reverse=True):
if shoot > e:
shoot = s
ret += 1
return ret