457. The Longest Chain of Pairs

Each pair (a, b) satisfies a < b. Pair (c, d) may FOLLOW pair (a, b) when b < c. Print the length of the longest chain that can be formed, choosing pairs in any order.

(1,2) (7,8) (4,5) -> 3 (1,2) (2,3) (3,4) -> 2 2 < 2 is false, so those two cannot be adjacent

Note the pairs may be used in any order, so this is not a subsequence problem despite looking like one. That is the first thing to notice.

Sorting by first element and running the O(n^2) longest-increasing-subsequence scan works. There is a better answer, and this problem is here because the better answer is NOT dynamic programming at all.

Sort by SECOND element ascending, then take greedily: keep any pair whose first element exceeds the last kept second element.

Why that is optimal is an exchange argument. Among all chains, consider one of maximum length. Its first pair can be replaced by the pair with the smallest second element without breaking anything, since that pair ends no later and so leaves at least as much room. Repeating the argument along the chain turns any optimal chain into the greedy one, so the greedy chain is also of maximum length.

Sorting by the FIRST element and taking greedily is wrong, because a pair that starts early may end very late and block everything after it. (1,100) (2,3) (4,5) is in the tests for that: first-element greedy takes (1,100) and stops at 1, while the answer is 2.

Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ a < b ≤ 1000000000`