365. Minimum Number of Arrows to Burst Balloons
A row of balloons is taped to a wall, each one covering a horizontal stretch of the x-axis. Balloon i is given as points[i] = [start, end] and spans every coordinate x with start <= x <= end (vertical position is irrelevant).
You fire arrows straight up from the x-axis. An arrow shot at position x pops every balloon whose stretch contains x — including balloons that only touch it at an endpoint — and keeps flying forever. Arrows are unlimited, but you want to use as few as possible.
Your function receives the list points and returns the minimum number of arrows needed to pop every balloon.
Example 1:
Input: points = [[10, 16], [2, 8], [1, 6], [7, 12]]
Output: 2
Explanation: An arrow at x = 6 pops [1, 6] and [2, 8]; an arrow at x = 12 pops [7, 12] and [10, 16].
Example 2:
Input: points = [[1, 2], [3, 4], [5, 6], [7, 8]]
Output: 4
Explanation: No two balloons overlap, so no arrow can pop more than one — four arrows are unavoidable.
Example 3:
Input: points = [[1, 2], [2, 3], [3, 4], [4, 5]]
Output: 2
Explanation: Touching endpoints count: an arrow at x = 2 pops [1, 2] and [2, 3], and an arrow at x = 4 pops [3, 4] and [4, 5].
Constraints:
- 1 ≤ points.length ≤ 10⁵
- -10⁹ ≤ start ≤ end ≤ 10⁹
Hints:
Two balloons can share an arrow exactly when their stretches overlap — and touching at a single point counts. Which balloon forces you to commit to an arrow first?
Sort by right endpoint. The first balloon must be popped by some arrow at x <= its right end; firing exactly at that right end pops it and every balloon whose start is at or before that x. Repeat from the next balloon still standing.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: points = [[10, 16], [2, 8], [1, 6], [7, 12]]
Expected output: 2