leetExpert
Practice

Minimum Number of Arrows to Burst Balloons

Module 21 · Intervals

Problem

Balloons are taped to a wall. Balloon i spans the horizontal range [start, end] (its width). You shoot arrows straight up from points on the x-axis; an arrow shot at x bursts every balloon whose range contains x (i.e. start <= x <= end). Return the minimum number of arrows needed to burst all balloons.

Examples

Example 1

Input[[10,16],[2,8],[1,6],[7,12]]Output2

Explanation. arrow at x=6 bursts [2,8],[1,6]; arrow at x=11 bursts [10,16],[7,12]

Example 2

Input[[1,2],[3,4],[5,6],[7,8]]Output4

Explanation. no shared x — one arrow each

Example 3

Input[[1,2],[2,3],[3,4],[4,5]]Output2

Explanation. arrow at x=2 and x=4

Constraints

1 ≤ n ≤ 10⁵ · endpoints fit in a 32-bit integer · touching endpoints count as overlapping (an arrow at a shared endpoint bursts both).

Attempt it first

If you solved Non-overlapping Intervals in the previous lesson, you have already written this algorithm — you just called it something else. Reframe: an arrow bursts a maximal group of balloons that all share at least one common x. So "minimum arrows" is "minimum number of groups such that every balloon in a group has a common piercing point." Try to see that this is the same sort-by-end greedy before opening the hint.