Balloons are taped to a wall, and balloon i spans the horizontal range points[i] = [start, end]. An arrow shot straight up at position x bursts every balloon with start <= x <= end. Return the minimum number of arrows needed to burst all balloons.
x = 6 (bursts [2,8] and [1,6]) and at x = 11 (bursts [10,16] and [7,12]).- 1 <= points.length <= 10^5
- points[i].length == 2
- -2^31 <= start < end <= 2^31 - 1
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Trying all arrow positions is far too slow. Sort by end. The balloon that ends first must be hit somewhere inside its range, and shooting at its end is the best choice: any other position in its range bursts a subset of what the end position bursts among the remaining balloons (they all end later, so moving right only helps). So the greedy is safe. After shooting at arrow = end, every balloon with start <= arrow is already burst. The first balloon with start > arrow needs a new arrow at its own end.
Algorithm
- Sort
pointsby end. - Shoot the first arrow at
points[0][1]and setarrows = 1. - For each next balloon: if
start > arrow, shoot a new arrow at its end and add 1. - Return
arrows.
O(n log n)Space: O(1) extra besides the sort(a, b) -> a[1] - b[1]: with values near -2^31 and 2^31 - 1 the subtraction overflows and the sort becomes wrong. Use Integer.compare.class Solution: def findMinArrowShots(self, points: List[List[int]]) -> int: points.sort(key=lambda p: p[1]) # by end arrows = 1 arrow = points[0][1] # shoot at the end of the first balloon for s, e in points[1:]: if s > arrow: # not burst by the last arrow arrows += 1 arrow = e return arrows