Introduction to Greedy Algorithm

You are given pairs [a, b]. One pair can follow another only when its start is greater than the earlier pair's end.

Find the longest chain.

[[1, 2], [7, 8], [2, 4], [4, 6]]    longest chain length = 3

Trying every possible order is far too slow.

Which pair should we choose first?

Choose the pair that ends earliest. It leaves the most room for later pairs.

Sort all pairs by end value. Then scan from left to right and accept each pair that starts after the last chosen end.

sorted:       [1,2] [2,4] [4,6] [7,8]
take [1,2]
skip [2,4]
take [4,6]
take [7,8]