Minimum Number of Arrows to Burst Balloons
Use the minimum arrows to burst all balloon intervals.
Pattern fit
This is interval scheduling in disguise: one arrow can cover an overlap cluster, so the greedy choice is to shoot at the earliest ending boundary.
Key observation
If two balloons overlap, one arrow at the common overlap can handle both, so only the overlap boundary matters.
Target complexity
O(n log n) / O(1)
How to break down the solution cleanly
This is interval scheduling in disguise: one arrow can cover an overlap cluster, so the greedy choice is to shoot at the earliest ending boundary.
If two balloons overlap, one arrow at the common overlap can handle both, so only the overlap boundary matters.
Identify the local choice that seems to preserve the most future flexibility.
Sort or preprocess if that makes the choice testable.
Reference implementation
Python# Generic pattern template
items.sort(key=priority)
answer = 0
for item in items:
if can_take(item):
take(item)
answer = update(answer)
Common pitfalls
Resetting the arrow position incorrectly when intervals overlap.
Sorting but still treating each interval independently.
Common follow-ups
Why is the end boundary the right greedy anchor?
How is this different from counting non-overlapping intervals?
Continue with related problems
Build repeatable depth inside the Greedy cluster before moving on.