Approach #1: Brute Force [Time Limit Exceeded]
Intuition and Algorithm
Let A
be the given array. Because the final chain has elements in sorted order, adding to our answer by considering A
in sorted order must achieve the correct final result.
Let tails[j] = k
indicate that a chain ending on j
has maximum length k
. At each interval (j, k)
, we try to add it to all our current considered chains, including the chain (j, k)
of length 1.
Python
class Solution(object):
def findLongestChain(self, A):
A.sort()
tails = {float('inf'): 0}
for j, k in A:
for i in tails.keys():
if i < j:
tails[k] = max(tails.get(k, 0), tails[i] + 1)
tails[k] = max(tails.get(k, 0), 1)
return max(tails.values())
Complexity Analysis

Time Complexity: $$O(N^2)$$, where $$N$$ is the length of the given array. The sorting step is $$O(N \log N)$$, which is dominated by the other steps. In the rest of the code, each interval considered in the outer loop "
for j, k in A
", we run through an inner loop "for i in tails.keys()
" with amortized complexity $$O(N)$$, which is in total $$O(N^2)$$. 
Space Complexity: $$O(N)$$. We need $$O(N)$$ space to store intermediate results related to
tails
.
Approach #2: Dynamic Programming, Naive Variation [Time Limit Exceeded]
Intuition and Algorithm
Again as in Approach #1, we only need to consider elements from A
in sorted order.
Let dp[i]
be the length of a longest chain ending at A[i][1]
.
Then, dp[i]
equals $\max\limits_{j < i}(dp[j] + 1 \text{  } A[j][1] < A[i][0])$, or dp[i] = 1
if no j
exists.
We can use bottomup dynamic programming to calculate the answer based on this recursion.
Python
class Solution(object):
def findLongestChain(self, A):
A.sort()
dp = [1] * len(A)
for i in range(len(A)):
for j in range(i):
if A[j][1] < A[i][0]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
Complexity Analysis

Time Complexity: $$O(N^2)$$, where $$N$$ is the length of the given array. The complexity comes from the two for loops in the code. The sorting step is $$O(N \log N)$$, but is dominated by the other steps.

Space Complexity: $$O(N)$$. We need $$O(N)$$ space to store the array
dp
.
Approach #3: Dynamic Programming, Bisection Variation [Time Limit Exceeded]
Intuition and Algorithm
Again as in Approach #1, we only need to consider elements from A
in sorted order.
Let dp[i]
be the smallest endpoint for a chain of length i
. As we consider intervals in sorted order, we will maintain this invariant.
Then, dp[i]
is increasing, and whenever we see an interval (x, y)
with dp[i1] < x
, we know that we can possibly extend the chain ending in dp[i1]
to the new candidate dp[i] = y
.
We can use a binary search to find the first such x
. If we have a new longest chain, then instead of modifying dp[i] = y
we will add y
to the end of dp
.
At the end, len(dp)  1
is the length of the largest chain we found.
Python
class Solution(object):
#def bisect_left(A, x):
# lo, hi = 0, len(A)
# while lo < hi:
# mid = (lo + hi) // 2
# if A[mid] < x: lo = mid + 1
# else: hi = mid
# return lo
def findLongestChain(self, A):
dp = [float('inf')]
for x, y in sorted(A):
i = bisect.bisect_left(dp, x)
if ix == len(dp):
dp.append(y)
elif y < dp[i]:
dp[i] = y
return len(dp)  1
Complexity Analysis

Time Complexity: $$O(N\log N)$$, where $$N$$ is the length of the given array. We need to sort the array, with complexity $$O(N\log N)$$. After, we iterate through an outer loop of complexity $$O(N)$$, and our inner binary search is $$O(\log N)$$. The final complexity is $$O(N\log N + N * \log N) = O(N \log N)$$.

Space Complexity: $$O(N)$$. We need $$O(N)$$ space to store the array
dp
.
Approach #4: Greedy [Accepted]
Intuition
If our current longest length chain ends in z
, and we have already processed all intervals (i, j)
with j < z
, then we do not need to consider smaller chains, because adding to our smaller chain would not make a larger length chain, and the right endpoint would be at least z
.
Algorithm
Sort the intervals by rightmost endpoint. If we can add to our current chain, then do so. After, we return the length of our chain.
Python
class Solution(object):
def findLongestChain(self, A):
A.sort(key = lambda (x, y): y)
right, ans = float('inf'), 0
for x, y in A:
if right < x:
right = y
ans += 1
return ans
Complexity Analysis

Time Complexity: $$O(N\log N)$$, where $$N$$ is the length of the given array. We need to sort the array, with complexity $$O(N\log N)$$; then iterate through it with complexity $$O(N)$$. Sorting dominates the complexity.

Space Complexity: $$O(1)$$ in additional space complexity. We need only to store the rightmost endpoint and the length of our current longest chain. (If we are not allowed to modify
A
, our answer would be $$O(N)$$ to store the sorted array.)