medium +25 pts

Minimum Number of Arrows to Burst Balloons

Find the fewest arrows needed to burst all overlapping balloons.

You are given a list of balloons, each represented as a list `[x_start, x_end]` (inclusive). An arrow shot at position `x` bursts any balloon whose interval contains `x`. Write a function `findMinArrowShots(points)` that returns the minimum number of arrows needed to burst all balloons. Implement the function: ```python def findMinArrowShots(points: list[list[int]]) -> int: ``` **Input**: A list `points` where each element is a pair `[x_start, x_end]` with `0 <= x_start <= x_end <= 10^9`. The list may be empty. The number of balloons is at most 10^5. **Output**: An integer, the minimum number of arrows required.

Constraints

0 <= len(points) <= 10^5 0 <= x_start <= x_end <= 10^9 Time: O(n log n) expected. Space: O(1) extra (sorts in place allowed).

Example

>>> findMinArrowShots([[10,16],[2,8],[1,6],[7,12]])
2
>>> findMinArrowShots([[1,2],[3,4],[5,6],[7,8]])
4
>>> findMinArrowShots([[1,2],[2,3],[3,4],[4,5]])
2
>>> findMinArrowShots([])
0
25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Sort intervals by their end coordinate.
Greedily shoot the arrow at the end of the first balloon; then skip all balloons it bursts.
When you encounter a balloon starting after the current arrow, shoot a new arrow at its end.
Python 3
All tests passed!
Test Results
Press Ctrl+Enter or click Run Tests to execute your code.