Minimum Number of Arrows to Burst Balloons
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
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;}