Loading...
Loading...
Loading...
Balloons hang along a line. Balloon i covers positions from a to b, ends included. An arrow shot at position x bursts every balloon whose range contains x. Print the fewest arrows needed to burst all balloons.
Example 1
Input
4 10 16 2 8 1 6 7 12
Output
2
Example 2
Input
4 1 2 3 4 5 6 7 8
Output
4
Try the problem first. Open one hint at a time.
An arrow at the right end of a balloon is never worse than one further left.
Sort by right end, shoot at the first balloon's end, and skip every balloon that starts at or before that point.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor