Minimum Number of Arrows to Burst Balloons

Problem

Each balloon is described by a horizontal interval points[i] = [start, end], meaning it spans the x-range start to end (inclusive). Arrows are shot straight up from an x-coordinate; an arrow shot at x bursts every balloon whose interval contains x, i.e. every balloon with start <= x <= end. An arrow keeps travelling upward and can burst any number of overlapping balloons.

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

Examples

• points = [[10,16],[2,8],[1,6],[7,12]] → 2 — one arrow at x = 6 bursts [2,8] and [1,6]; one arrow at x = 12 bursts [10,16] and [7,12].
• points = [[1,2],[3,4],[5,6],[7,8]] → 4 — no two intervals overlap, so each needs its own arrow.
• points = [[1,2],[2,3],[3,4],[4,5]] → 2 — an arrow at x = 2 bursts [1,2],[2,3]; an arrow at x = 4 bursts [3,4],[4,5].

Constraints

• 1 <= len(points) <= 10^5
• points[i] = [start, end] with start <= end, values fitting in 32-bit signed range.
• The 10^5 bound (and huge coordinate range) means an O(n log n) sort-then-scan is the target; enumerating arrow positions is out.

Think about it first

TL;DR

Sort by right endpoint, then sweep: shoot an arrow at each new interval’s end and skip everything it covers — greedy interval point-cover, O(n log n) time, O(1) extra space.

Approach 1 — Brute force (search over candidate arrow positions)

An optimal arrow can always be moved to sit on some balloon’s endpoint, so the endpoints are the only candidate positions worth considering. Naively, try every subset of candidate positions from smallest to largest size, and return the first subset that stabs all balloons.

from itertools import combinations
from typing import List


class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        candidates = sorted({p[1] for p in points})
        n = len(candidates)
        for k in range(1, n + 1):
            for arrows in combinations(candidates, k):
                if all(any(s <= x <= e for x in arrows) for s, e in points):
                    return k
        return n  # one arrow per balloon in the worst case

Complexity: O(2^n · n^2) time — exponential in the number of balloons.

With n up to 10^5 this is hopeless; it only pins down that endpoints are the positions that matter.

Approach 2 — Greedy (sort by end, shoot at the earliest end)

This is the classic interval point-cover / activity-selection greedy: to stab all intervals with fewest points, sort by right endpoint and always place a point at the current earliest-ending interval’s right end.

Greedy-choice property (why the local decision is globally optimal). Consider the balloon that ends earliest, at x = e_min. Some arrow must burst it, and any arrow that bursts it sits at a position p <= e_min (since p must be <= e_min to be inside that balloon). Sliding that arrow rightward to exactly e_min keeps it inside the earliest balloon and can only add coverage of other balloons (their intervals extend to the right of e_min if they overlap it at all) — it never loses a balloon. So there is an optimal solution that shoots at e_min. This is a standard exchange argument: any optimal arrow set can be transformed, arrow by arrow, into one that shoots at earliest ends, without increasing the count. Having committed the first arrow greedily, the balloons it bursts are removed and the same argument applies to the rest.

from typing import List


class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        if not points:
            return 0

        points.sort(key=lambda p: p[1])   # by right endpoint
        arrows = 1
        arrow_x = points[0][1]            # shoot at first balloon's end

        for start, end in points[1:]:
            if start > arrow_x:           # this balloon starts after the arrow
                arrows += 1               # need a new arrow
                arrow_x = end             # placed at this balloon's end
        return arrows

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

Sorted by end → [[1,6],[2,8],[7,12],[10,16]].

Answer: 2.

Complexity: O(n log n) time (dominated by the sort), O(1) extra space beyond the sort.

Note on the strict > comparison: because balloons burst at touching endpoints too (interval is inclusive), start == arrow_x still bursts, so only start > arrow_x forces a new arrow.

Common pitfalls

• Sorting by start instead of end. Sorting by start and greedily extending can over-count; the earliest-end balloon is the one that constrains the arrow, so sort by end.
• Using >= instead of > for the “need a new arrow” test. Endpoints are inclusive, so a balloon starting exactly at the arrow’s x is still burst.
• Integer overflow in languages with fixed-width ints when computing midpoints — here we never average endpoints, we shoot at the end directly, sidestepping it.
• Forgetting the empty-input guard (findMinArrowShots([]) == 0).

Pattern takeaway

For “cover / stab all intervals with the fewest points” (and its twin, “select the most non-overlapping intervals”), sort by right endpoint and greedily commit to the earliest end. The exchange argument — any optimal point can slide to the earliest end without losing coverage — is the reusable justification for this whole family of interval-scheduling greedies.