hardGreedyPure DSA~30 min
Fewest Shots to Burst All Overlapping Intervals
Balloons span horizontal intervals; a single vertical arrow at position x bursts every balloon whose interval covers x. Find the minimum number of arrows to burst them all.
Problem
Given points where points[i] = [start, end] is the horizontal span of a balloon, an arrow shot at x bursts a balloon if start <= x <= end. Return the minimum number of arrows required to burst all balloons.
Input
A list points of [start, end] intervals.
Output
An integer: the minimum number of arrows.
Constraints
- 1 <= points.length <= 10^5
- -2^31 <= start <= end <= 2^31 - 1
- Endpoints are inclusive.
Examples
Example 1
Input
points = [[10,16],[2,8],[1,6],[7,12]]
Output
2
One arrow at 6 bursts [1,6] and [2,8]; another at 11 bursts the rest.
Example 2
Input
points = [[1,2],[3,4],[5,6],[7,8]]
Output
4
No intervals overlap, so each needs its own arrow.