Problem Statement

Minimum Number of Arrows to Burst Balloons

Picture balloons taped to a wall. Each balloon covers a stretch of the wall from a start point to an end point, like [1,6] means it covers everything from 1 to 6. You shoot arrows straight up. An arrow shot at position x pops a balloon if x lands anywhere inside that balloon's stretch (start <= x <= end). One arrow can pop many balloons at once if they all overlap at the spot you aim. The question: what is the smallest number of arrows that pops every balloon? The trick is to be smart about where each arrow goes so one arrow covers as many balloons as possible. We do that with a greedy approach. Greedy means we make the best-looking choice at each step and never go back to change it. Here the good choice is to sort the balloons by where they end, then aim each arrow at the end of a balloon, which catches the most overlapping balloons in one shot.

mediumGreedySortingGreedyTime: O(n log n) · Space: O(1)

Signals to notice

minimum arrows to burst all balloonsoverlapping intervalsone arrow pops all overlapping

Brute force first

Try all arrow positions. Test every possible x-coordinate. That instinct is useful because it follows the prompt literally, but it usually keeps revisiting work the problem is begging you to organize.

The key insight

Sort by end coordinate. Shoot at each balloon's end. Skip all balloons that overlap with this shot. Count arrows. The goal is not to be clever for its own sake, but to remember the one relationship that keeps the solution grounded as you move forward.

Trace it on `points=[[10,16],[2,8],[1,6],[7,12]]`

sort by end -> [[1,6],[2,8],[7,12],[10,16]]
init: arrows=1, arrow_pos=6 (end of [1,6])
i=1 [2,8]: start 2 > 6? no -> covered, no change
i=2 [7,12]: start 7 > 6? yes -> arrows=2, arrow_pos=12
i=3 [10,16]: start 10 > 12? no -> covered, no change
return arrows = 2

What must stay true

Shooting at a balloon's end maximizes the chance of hitting overlapping balloons to the right. If the next balloon starts after the shot, it needs a new arrow. If that remains true after every update, the rest of the reasoning has a stable place to stand.

Shape of the loop

sort points by end coordinate ascending
arrows = 1; arrowPos = points[0].end
for p in points[1:]:
    if p.start > arrowPos:        # current arrow can't reach it
        arrows += 1; arrowPos = p.end
return arrows

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Sorting by start instead of end — end-sorting ensures the greedy choice covers the maximum number of subsequent overlapping balloons. When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.

Greedy Pattern