All problems

Minimum Arrows to Burst Balloons

Medium · intervals

Balloons are taped flat to a long wall. The balloon balloons[i] = [start, end] covers the stretch of wall from start to end, both ends included.

An arrow is shot straight up from a point x on the floor. It bursts every balloon whose stretch contains x, which means start <= x <= end. An arrow that touches only the edge of a balloon still bursts it. Arrows keep flying, so one arrow can burst any number of balloons.

Return the smallest number of arrows needed to burst every balloon.

Examples

Example 1

Input: balloons = [[1, 5], [4, 9], [8, 12], [20, 25]]

Output: 3

One arrow at 4 or 5 bursts the first two balloons, one at 8 to 12 bursts the third, and the last balloon is far away, so it needs its own.

Example 2

Input: balloons = [[2, 4], [4, 6], [6, 8]]

Output: 2

An arrow at 4 bursts the first two balloons because both include 4. The third balloon needs another arrow.

Example 3

Input: balloons = [[1, 2], [1, 2], [1, 2]]

Output: 1

The three balloons sit on exactly the same stretch, so a single arrow bursts them all.

Constraints