There are n balloons, each covering a closed interval [l, r] on a number line. An arrow shot at coordinate x pops every balloon whose interval contains x (that is, l <= x <= r). Arrows are vertical and travel infinitely, so a single arrow at x pops all balloons spanning x.
Return the minimum number of arrows needed so that every balloon is popped.
Line 1: an integer n, the number of balloons.
Next n lines: two integers l and r (with l <= r), one balloon per line.
A single integer: the minimum number of arrows that pops all balloons.
Example 1
Input
4 1 6 2 8 7 12 10 16
Expected
2
Explanation
An arrow at 6 pops [1,6] and [2,8]; an arrow at 12 pops [7,12] and [10,16]. Two arrows suffice and one cannot pop all four, so the answer is 2.
Example 2
Input
3 1 2 3 4 5 6
Expected
3
Explanation
The three intervals are pairwise disjoint, so no single arrow hits two of them. Three arrows are required.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →