Minimum Arrows to Burst Balloons

Difficulty: Hard · Topic: Greedy algorithms

Each balloon is an interval [start, end]; an arrow shot at x bursts every balloon with start ≤ x ≤ end. Return the minimum number of arrows to burst all balloons. Sort by end, shoot at the first end, and skip every balloon that arrow already bursts.

Examples

min_arrows([[10,16],[2,8],[1,6],[7,12]])
→ 2

Arrows at 6 and 12.

min_arrows([[1,2],[3,4],[5,6],[7,8]])
→ 4

Target complexity: time O(n log n), space O(1)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.