Minimum Number of Arrows to Burst Balloons

You are given intervals representing balloons. Each balloon is [x_start, x_end]. An arrow shot at position x bursts all balloons where x_start <= x <= x_end.

Return the minimum number of arrows needed to burst all balloons.

Function signature

func FindMinArrowShots(points [][]int) int

Inputs / outputs

• points: list of balloon intervals.
• Return: minimum number of arrows.

Example

points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2

Arrows at x=6 and x=12.

Constraints

• 0 <= len(points) <= 100_000
• -1_000_000_000 <= x_start <= x_end <= 1_000_000_000

Core idea (near-solution)

Sort by end coordinate and greedily shoot an arrow at the end of the first balloon, then skip all balloons it bursts.

Invariant: the current arrow position is the smallest possible end that can still burst all balloons chosen so far.

Algorithm (step-by-step)

1. Sort balloons by end ascending.
2. Initialize arrows = 0 and lastEnd = -inf.
3. For each balloon:
   • If start > lastEnd, you need a new arrow. Increment arrows and set lastEnd = end.
   • Else, it is already burst by the current arrow.
4. Return arrows.

Correctness sketch

• Invariant: the current arrow position is the smallest possible end that can still burst all balloons chosen so far.
• Sorting establishes a consistent processing order.
• Merge/greedy steps maintain a correct partial solution.
• After processing all intervals, the result is optimal and complete.

Trace (hand walkthrough)

Example input:
points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2

Arrows at x=6 and x=12.

Walk:
- sort by end: [1,6],[2,8],[7,12],[10,16]
- arrow at x=6 bursts first two
- next arrow at x=12 bursts last two -> total 2

Pitfalls to avoid

• Sorting by start instead of end.
• Using >= instead of > for overlap (touching at a point should be considered burst).

Complexity

• Time: O(n log n)
• Extra space: O(n) for sorting.

Implementation notes (Go)

• Sort by end coordinate.
• Start a new arrow only when start > currentEnd.