Minimum Number of Arrows to Burst Balloons

Explanation & Solution

Description

There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend. You do not know the exact y-coordinates of the balloons.

Arrows can be shot up exactly vertically (in the positive y-direction) from different points along the x-axis. A balloon with xstart and xend is burst by an arrow shot at x if xstart <= x <= xend. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloon in its path.

Given the array points, return the minimum number of arrows that must be shot to burst all balloons.

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

Output: 2

Explanation: The balloons can be burst by 2 arrows: shoot an arrow at x = 6 (bursts balloons [2,8] and [1,6]) and another arrow at x = 12 (bursts balloons [10,16] and [7,12]).

Constraints

1 <= points.length <= 10^5
points[i].length == 2
-2^31 <= xstart < xend <= 2^31 - 1

Approach

Intervals pattern

1. Sort by End Coordinate

Sort the points array by each balloon's end coordinate (xend) in ascending order
This ensures we always consider the balloon that ends earliest first

2. Shoot the First Arrow

Initialize arrows = 1 and set arrowPos = points[0][1] (the end of the first balloon)
We shoot our first arrow at the rightmost point of the first balloon in sorted order

3. Iterate Through Remaining Balloons

For each subsequent balloon, check if its start (points[i][0]) is greater than the current arrowPos
If start > arrowPos: the current arrow cannot reach this balloon, so we need a new arrow
If start <= arrowPos: this balloon is already burst by the current arrow — skip it

4. Place New Arrows Greedily

When a new arrow is needed, increment arrows and set arrowPos = points[i][1] (shoot at this balloon's end)
This greedy placement maximizes the chance of bursting future balloons with the same arrow

5. Return the Count

After processing all balloons, arrows holds the minimum number of arrows needed

Key Insight

The greedy choice of always shooting at the rightmost point (end coordinate) of the first un-burst balloon is optimal because it gives the arrow the maximum chance of overlapping with subsequent balloons
Sorting by end coordinate guarantees that once a balloon's start exceeds our arrow position, no future balloon in sorted order can be reached by the current arrow
The overall complexity is O(n log n) due to sorting, with O(1) extra space (sorting is in-place)

Visualization

Input:

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

—

Press play to start visualization

CurrentCompareOverlapMerged

9 steps

Solution Code

Task Scheduler

Employee Free Time