Fewest Arrows to Pop the Balloons

Balloons are stuck to a long wall. Seen from the front, balloon i covers the stretch of the wall from balloons[i][0] to balloons[i][1], both ends included. An archer stands on the floor and shoots arrows straight up: an arrow shot at position x pops every balloon whose stretch contains x, and it keeps flying after popping one.

Write fewest_arrows(balloons) that returns the smallest number of arrows needed to pop every balloon.

Examples

fewest_arrows([(1, 6), (2, 8), (7, 12), (10, 16)])  # returns 2
fewest_arrows([(1, 2), (3, 4), (5, 6)])             # returns 3
fewest_arrows([(1, 2), (2, 3), (3, 4)])             # returns 2

In the first example an arrow at 6 pops the first two balloons and an arrow at 11 pops the other two. In the last example an arrow at 2 pops the first two balloons, because touching ends count.

Constraints

• 0 <= len(balloons) <= 100,000
• Each balloon is a pair (start, end) of whole numbers with -10^9 <= start <= end <= 10^9