Minimum Number of Arrows to Burst Balloons

Medium· Sorting· Activity Selection

Problem

Each balloon spans a horizontal range [xstart, xend]. An arrow shot straight up at position x bursts every balloon whose range includes x, endpoints included. Return the minimum number of arrows needed to burst all balloons.

Examples

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

Output: 2

An arrow at x = 6 bursts [2,8] and [1,6]; one at x = 11 bursts [10,16] and [7,12].

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

Output: 4

Constraints

• 1 <= points.length <= 10^5
• -2^31 <= xstart < xend <= 2^31 - 1

Hints & approach

Hint 1

Shooting at the right edge of some balloon is never worse than shooting further left.

Hint 2

Sort by end and shoot at the end of the first balloon not yet burst.

Approachtry the hints first

Sort balloons by their end. Fire the first arrow at the end of the first balloon. For each subsequent balloon, if its start is at or before the last arrow position it is already burst; otherwise fire a new arrow at its end. Placing each arrow as far right as possible covers the most later balloons. Compare values rather than subtracting to avoid overflow in languages with fixed-width integers.

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

← PreviousNon-overlapping Intervals Next →Minimum Interval to Include Each Query