#452 - Minimum Number of Arrows to Burst Balloons

MediumIntervals

Balloons are represented as intervals [xstart, xend] on a wall. An arrow shot at position x bursts all balloons where xstart <= x <= xend. Return the minimum number of arrows to burst all balloons.

Input	Output
points = [[10,16],[2,8],[1,6],[7,12]]	2
points = [[1,2],[3,4],[5,6],[7,8]]	4
points = [[1,2],[2,3],[3,4],[4,5]]	2

Solution Space

Try it

/**
 * Returns the minimum number of arrows to burst all balloons.
 * Greedy: sort by end, shoot at the end of the earliest-ending balloon.
 *
 * @param points Array of [xstart, xend] balloon intervals
 * @returns Minimum arrows
 */
export function findMinArrowShots(points: number[][]): number {
  points.sort((a, b) => a[1] - b[1]);

  let arrows = 1;
  let arrowPos = points[0][1];

  for (let i = 1; i < points.length; i++) {
    if (points[i][0] > arrowPos) {
      // This balloon isn't hit by the current arrow — need a new one
      arrows++;
      arrowPos = points[i][1];
    }
  }

  return arrows;
}

Approach: greedy by end point – sort by `xend`. Place each arrow at the end of the current earliest-ending balloon. Any balloon whose start > arrow position needs a new arrow.

Time: O(n log n) – sorting dominates.

Space: O(1) extra – sorting in place.

#435 Non-overlapping Intervals

#739 Daily Temperatures