Minimum Number of Arrows to Burst Balloons

Medium

Problem

Each balloon spans [xstart, xend] on the x-axis. An arrow shot straight up at x bursts every balloon with xstart ≤ x ≤ xend. Return the minimum number of arrows needed to burst them all.

Example 1

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

Shoot at x = 6 and x = 11.

Test cases

Case 1

Input:    [[10,16],[2,8],[1,6],[7,12]]
Expected: 2

Case 2

Input:    [[1,2],[3,4],[5,6],[7,8]]
Expected: 4

Case 3

Input:    [[1,2],[2,3],[3,4],[4,5]]
Expected: 2

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Sort by end, shoot at the end

Time O(n log n)Space O(1) extra

Shoot at the end of the earliest-ending balloon; it bursts every balloon starting at or before that point. Shoot again only when a balloon starts after it.

function findMinArrowShots(points) {
points.sort((a, b) => a[1] - b[1]);
let arrows = 0, pos = -Infinity;
for (const [s, e] of points) {
if (s > pos) { arrows++; pos = e; }
}
return arrows;
}