Minimum Arrows to Burst Balloons

Problem Statement

Balloons are represented as horizontal intervals [x_start, x_end]. A vertical arrow shot at position x bursts every balloon whose range contains x. Return the minimum number of arrows needed to burst every balloon.

Input

An array points where each entry is a balloon’s horizontal span.

[[10,16],[2,8],[1,6],[7,12]]

Output

A single integer — the minimum number of arrows.

2

Constraints

• 1 ≤ points.length ≤ 10⁵
• points[i].length == 2
• -2³¹ ≤ xstartᵢ ≤ xendᵢ ≤ 2³¹ − 1

Intuition

Sort by end coordinate. Shoot the first arrow at the first balloon’s right edge — it automatically pops every balloon that starts at or before that edge. The next balloon whose start exceeds the arrow position begins a new group → another arrow. This is exactly the Activity Selection problem, counting groups instead of kept intervals.

Sort by end:  [1,6]  [7,12]  [10,16]  [2,8]
                ↑      ↑        ↑       ↑
Arrow at 6:   BURST  (start 7 > 6, new group)
Arrow at 12:         BURST   BURST    BURST (start 2 ≤ 12)
 
Total arrows: 2

Solution

def findMinArrowShots(points: list[list[int]]) -> int:
    if not points:
        return 0
 
    points.sort(key=lambda x: x[1])
    arrows, pos = 1, points[0][1]
 
    for start, end in points[1:]:
        if start > pos:
            arrows += 1
            pos = end
 
    return arrows

function findMinArrowShots(points: number[][]): number {
    if (points.length === 0) return 0;
 
    points.sort((a, b) => a[1] - b[1]);
    let arrows = 1, pos = points[0][1];
 
    for (let i = 1; i < points.length; i++) {
        if (points[i][0] > pos) {
            arrows++;
            pos = points[i][1];
        }
    }
 
    return arrows;
}

Complexity

Edge Case Thinking