PreviousNext
Coding/Searching and sorting

Burst balloons with arrows

Write codeMedium20 min

Your task

Given a list of closed intervals points[i] = [start, end] representing balloons on a number line, you shoot arrows straight up. An arrow at x-coordinate p bursts every balloon whose interval contains p (start <= p <= end, inclusive on both ends). Return the minimum number of arrows needed to burst all balloons. Up to 10^5 intervals; coordinates are 32-bit ints. This is the minimum-stabbing-points problem, sort by end and greedily place arrows.

Examples

min_arrows(points: list[list[int]]) -> int
Example 1
Inputmin_arrows([[10, 16], [2, 8], [1, 6], [7, 12]])
Output2