1094. One Arrow Per Cluster

n balloons float in a row. Balloon i spans the closed stretch [l, r], and an arrow fired at position x bursts every balloon with l <= x <= r.

Print the fewest arrows that burst every balloon, and then the positions they are fired at, chosen by this exact rule:

> repeatedly take the SMALLEST right endpoint among the balloons not yet burst, and > fire there.

The rule matters because a smallest set of arrows is not unique: with the single balloon [0, 5] any one position from 0 to 5 works. Fixing the rule makes the answer a single definite list, and the list it produces is always of smallest possible size.

balloons [10,16] [2,8] [1,6] [7,12] -> 2 arrows at 6 and 12 balloons [1,2] [3,4] [5,6] [7,8] -> 4 arrows at 2, 4, 6, 8 balloons [1,2] [2,3] [3,4] [4,5] -> 2 arrows at 2 and 4

Trace the third line. The smallest right endpoint is 2, and firing there bursts [1,2] and [2,3], because a shared boundary still counts as a hit. Of what is left, [3,4] has the smallest right endpoint, so the second arrow goes to 4 and bursts [3,4] and [4,5]. Two arrows.

## What most people try first

Sorting by the LEFT endpoint and firing at the left end of the first balloon. That fails on [1,6] [2,8] [7,12] [10,16]: firing at 1 bursts only the first balloon, then at 2 only the second, and the answer comes out as 4 instead of 2.

Sorting by left endpoint and firing at the RIGHT end of the first balloon is closer but still wrong, because the first balloon by left endpoint may be a very wide one. [0,100] [1,2] [3,4] fires at 100, bursts only the wide balloon, then needs two more, for 3 where 2 suffice.

Trying every position is not an option either: coordinates run to 10^9.

## The method

sort the balloons by right endpoint last = none for each balloon (l, r) in that order: if last is none or l > last: fire at r last = r

One sort and one pass, O(n log n).

## Why firing at the smallest right endpoint is optimal

Let b be the balloon with the smallest right endpoint r. Every set of arrows must contain one that hits b, and that arrow sits somewhere in [l_b, r], so it sits at or before r.

Move that arrow to r. Which balloons could it lose? Only ones ending before r, and there are none, because r is the smallest right endpoint of all. Which balloons does it gain? Possibly several, since every balloon containing a point at or before r and extending past it now gets hit.

So the swapped set is still a full solution and is no larger. Delete b and every balloon that the moved arrow hits, and repeat the argument on what remains. After finitely many swaps any optimal set has been turned into the greedy set without growing, so the greedy set is smallest.

That is the exchange argument, and notice what it rests on: "ends earliest" is the property that makes a choice safe, not "starts earliest" and not "is shortest".

## The boundary that breaks a careless implementation

The test is l > last, strictly. A balloon whose left endpoint equals the last arrow's position is already burst, because the stretch is closed. Writing l >= last turns [1,2] [2,3] [3,4] [4,5] from 2 arrows into 4.

Zero-width balloons, where l == r, are legal and must still be hit.

## Sizes

Coordinates reach 10^9, which fits comfortably inside a signed 32-bit integer since 2147483647 is larger. Nothing here is added or multiplied, so 32 bits would be enough throughout; the arrow count is at most n.

## Related problems

Problem #1437 asks the mirror question on the same sorted-by-end sweep: how many intervals to DELETE so that none of the survivors overlap. There the answer is a count of what is thrown away; here it is a set of points, which is why this problem has to print positions and that one does not.

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ l ≤ r ≤ 1000000000`