⚡Flashcard Drill➔
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

  1. This is interval stabbing: minimise the number of points that hit every interval.
  2. Sort by end, then greedily place an arrow at the end of the first unbursted balloon.
  3. That arrow bursts every subsequent balloon whose start is at or before that end.
  4. 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 strict s > 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 = 1 would 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.
🎯 Drill This Card Now➔

🧩 Related Intervals Problems