Approach #1: Dynamic Programming [Accepted]
Intuition
If a chain of length k
ends at some pairs[i]
, and pairs[i][1] < pairs[j][0]
, we can extend this chain to a chain of length k+1
.
Algorithm
Sort the pairs by first coordinate, and let dp[i]
be the length of the longest chain ending at pairs[i]
. When i < j
and pairs[i][1] < pairs[j][0]
, we can extend the chain, and so we have the candidate answer dp[j] = max(dp[j], dp[i] + 1)
.
Complexity Analysis

Time Complexity: where is the length of
pairs
. There are two for loops, and dominates the sorting step. 
Space Complexity: for sorting and to store
dp
.
Approach #2: Greedy [Accepted]
Intuition
We can greedily add to our chain. Choosing the next addition to be the one with the lowest second coordinate is at least better than a choice with a larger second coordinate.
Algorithm
Consider the pairs in increasing order of their second coordinate. We'll try to add them to our chain. If we can, by the above argument we know that it is correct to do so.
Complexity Analysis

Time Complexity: where is the length of
S
. The complexity comes from the sorting step, but the rest of the solution does linear work. 
Space Complexity: . The additional space complexity of storing
cur
andans
, but sorting uses space. Depending on the implementation of the language used, sorting can sometimes use less space.
Analysis written by: @awice.