p84 — Minimum Number of Arrows to Burst Balloons

Source: LeetCode 452 · Medium · Topics: Greedy, Sorting, Intervals Companies (2024–2025): Amazon (high), Google (medium), Meta (medium) Loop position: Canonical interval-scheduling greedy — sort by END. Tests whether you can articulate why end-sort beats start-sort.

1. Quick Context

n balloons specified as [x_start, x_end]. An arrow shot at coordinate x bursts every balloon containing x. Return the min number of arrows.

Equivalent: Min arrows = max number of pairwise-disjoint intervals (after greedy partitioning into non-overlapping groups; each group bursts with one arrow).

Greedy: Sort by x_end. Track current arrow position (initially the first interval’s end). For each subsequent interval: if start > arrow, need a new arrow; update arrow = end.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/

STOP. 25-min timer. Don’t peek; derive why sort-by-end.

3. Prerequisite Concepts

• Activity selection / interval scheduling.
• Greedy correctness via exchange argument.

4. How to Approach (FRAMEWORK 1–9)

1. Restate: Cover all intervals with the minimum count of vertical-line “stabs”.

2. Clarify: Endpoints included? Yes (closed intervals). Empty input → 0.

3. Examples: [[10,16],[2,8],[1,6],[7,12]] → 2 (arrows at x=6 and x=12).

5. Brute: Try all subsets of “arrow positions” = endpoints; check covering. Exponential.

6. Target: O(n log n) sort + O(n) sweep.

7. Pattern: Sort by end; commit minimum-end first; greedy stab at that end.

8. Develop: see solution.py.

9. Test: all overlapping (1 arrow); all disjoint (n arrows); single balloon.

5. Progressive Hints

See hints.md.

6. Deeper Insight

6.1 Why sort by END, not start

Exchange argument. Suppose an optimal solution uses arrow at position a. Consider the interval with the smallest end that a covers. Moving a to that end (right edge) can only extend coverage rightward — every interval covered by a had start ≤ a ≤ end_min, so moving to end_min keeps those covered (since end_min ≤ end_i) AND may add more. So the greedy “stab at the smallest end” is optimal.

If we sort by start: [[1, 100], [2, 3], [4, 5]] — start-sort puts [1,100] first; greedy might stab at 100, missing [2,3] and [4,5]. Forced to think more carefully. End-sort makes the greedy choice obvious.

6.2 The arrow-position invariant

After sorting by end, walk left-to-right. The current arrow is at the end of the most recent “uncommitted” interval. Each new interval either:

• Starts at or before the arrow: covered by current arrow; skip.
• Starts after the arrow: needs a new arrow; advance arrow to this interval’s end.

6.3 Equivalence to “max disjoint intervals”

Min arrows = number of disjoint intervals you can carve out. Same greedy: sort by end, take intervals whose start > previous_end.

6.4 Edge case: touching endpoints

[[1, 2], [2, 3]]: x=2 bursts both. Greedy: sort by end → process [1,2] first, arrow=2; [2,3] has start=2 ≤ arrow=2 → no new arrow. Count=1. Correct.

6.5 Family: interval-scheduling greedy

• LC 452 Burst Balloons (this; min covers).
• LC 435 Non-overlapping Intervals (min removals to make disjoint).
• LC 56 Merge Intervals (sort by start; merge consecutive).
• LC 253 Meeting Rooms II (heap of end times; min rooms).

Pattern: sort by end for “max disjoint” / “min stab”; sort by start for “merge” / “scheduling overlap counts”.

6.6 Overflow gotcha

Endpoint values can be near INT_MIN/INT_MAX. In Python no overflow; in C++/Java, use long for comparisons or start > arrow (not arrow + 1 < start).

7. Anti-Pattern Analysis

1. Sort by start, then greedy — fails on [[1,100],[2,3],[4,5]].
2. Use arrow + 1 < start — overflow in fixed-width languages.
3. Try interval-merging then count — works but conceptually fuzzy.
4. Track all overlapping intervals at each x — quadratic.
5. Heap of intervals by start, popping when arrow position changes — overcomplicated; sweep suffices.
6. Forget to handle empty input — return 0.

8. Skills & Takeaways

• Sort-by-end + sweep template.
• Exchange argument for “stab at the smallest end”.
• Equivalence between min-cover and max-disjoint.

9. When to Move On

• Solve cold in 15 min, articulate the exchange argument.
• Justify end-sort vs start-sort with a counterexample.
• Cite Non-overlapping Intervals (LC 435) as a sibling.

10. Company Context

• Amazon: L4/L5; very common phone screen.
• Google: L5; expects exchange-argument justification.
• Meta: E4; calendar-scheduling flavor.

Strong: “Sort by end, sweep; cold; exchange-argument justified; cited Non-overlapping Intervals and Meeting Rooms II as siblings.”

11. Interviewer’s Lens

12. Level Delta

• Mid (L4): Sorts by start, fails; corrects after test; counts correctly.
• Senior (L5): Sorts by end cold; correct on touching ends; cites family.
• Staff (L6): + exchange-argument proof + max-disjoint equivalence + Meeting Rooms II generalization.
• Principal (L7+): + recognizes this as interval graph clique cover (NP-hard in general, polynomial for intervals via this exact greedy); + cites Helly’s theorem on the line (mutual pairwise overlap ⟹ common point).

13. Follow-up Q&A

Q1: Return the actual arrow positions, not just count. A1: Track them during the sweep — push current end to a list when we commit a new arrow.

Q2: What if intervals are open (exclusive endpoints)? A2: Change start > arrow to start >= arrow. Touching intervals no longer share an arrow.

Q3: 2D — disks instead of intervals, vertical arrows? A3: Project to x-intervals (disk i covers [cx-r, cx+r] for any vertical arrow at the projected y); same greedy in x. For general 2D point cover, NP-hard.

Q4: Weighted balloons — each requires an arrow with cost = weight? A4: Min-cost set cover; NP-hard in general. For intervals, LP relaxation is integral; solvable by DP.

Q5: Streaming — balloons arrive online? A5: Lower bound: 2-approximation by stabbing immediately at the right end of the first unstabbed interval seen.

14. Solution Walkthrough

See solution.py:

• find_min_arrow_shots — sort by end + sweep; O(n log n).
• find_min_arrow_shots_brute — try all subsets of endpoints as candidate arrow sets; oracle.

15. Beyond the Problem

Principal code review: “Burst Balloons is the canonical interval-clique-cover problem solved by an exchange argument. The interesting structural fact: on the real line, interval graphs are perfect — chromatic number equals clique number, max clique can be found in O(n log n) by sweep, and clique cover (this problem) equals max independent set on the complement (max disjoint intervals). This is not true in general graphs (clique cover is NP-hard). The Staff+ insight: when a problem reduces to a graph optimization, ask ‘is the graph in a structured class — interval, chordal, planar, bipartite?’ If yes, problems that are NP-hard in general become polynomial. The exchange argument here is the constructive witness of intervals’ perfection. The follow-up: the same problem on a circle (circular-arc graphs) is already harder — chromatic number is NP-hard in general, though the clique-cover version remains polynomial. Topology matters.”