NeetCode #841LC-452MediumIntervals
← Back to All Problems#841 · #452 · Minimum Number of Arrows to Burst Balloons(用最少数量的箭引爆气球)
📌 Problem Statement & Constraints
There are spherical balloons taped to a wall at
points[i] = [xstart, xend]. An arrow shot vertically at x bursts every balloon whose span contains x. Return the minimum number of arrows to burst all balloons. Constraints: 1 <= points.length <= 10^5, -2^31 <= xstart <= xend <= 2^31 - 1.💡 Core Algorithmic Approaches
- This is interval stabbing: minimise the number of points that hit every interval.
- Sort by end, then greedily place an arrow at the end of the first unbursted balloon.
- That arrow bursts every subsequent balloon whose start is at or before that end.
- Placing the arrow as far right as possible (at the earliest end) is optimal by the exchange argument, since it maximises the chance of catching later balloons.
💻 Benchmark Python3 Implementation
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
if not points:
return 0
points.sort(key=lambda x: x[1]) # earliest finishing first
arrows = 1
end = points[0][1] # the first arrow sits at this end
for s, e in points:
if s > end: # this balloon is not burst yet
arrows += 1
end = e
return arrows⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log n): the sort by end dominates.
💾 Space Complexity
O(1) beyond the sort.
⚠️ Interview Pitfalls & Follow-ups
- Using
s >= end: a balloon starting exactly at the arrow position is burst, so the test is stricts > end. - Sorting by start: the earliest-end greedy is the correct choice for stabbing.
- Shooting at the start instead of the end: the end maximises coverage of later balloons.
- Forgetting the empty input: with no balloons the answer is 0, and the initial
arrows = 1would be wrong without the guard.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.