**Maximum Length of Pair Chain** https://leetcode.com/problems/maximum-length-of-pair-chain/#/description

**LIS variant using O(N^2) time and O(N) space**

- Simply sort the array and apply LIS algorithm over it.

```
class Solution:
def findLongestChain(self, pairs):
"""
:type pairs: List[List[int]]
:rtype: int
"""
pairs.sort(key = lambda x:(x[0], x[1]))
LIS = [1]*len(pairs)
for i in range(1, len(pairs)):
for j in range(i):
LIS[i] = max(LIS[i], LIS[j]+1) if pairs[j][1] < pairs[i][0] else LIS[i]
return LIS[-1]
```

**O(Nlg(N)) with O(N) space solution**

- Variant of the binary search solution for LIS problem. details: https://discuss.leetcode.com/topic/75189/python-solution-with-detailed-explanation

```
from bisect import bisect_left
class Solution:
def findLongestChain(self, pairs):
"""
:type pairs: List[List[int]]
:rtype: int
"""
pairs.sort(key = lambda x:x[0])
tails = []
for p in pairs:
idx = bisect_left(tails, p[1])
if idx == len(tails):
if len(tails) == 0 or (idx>=1 and p[0] > tails[idx-1]):
tails.append(p[1])
else:
tails[idx] = p[1]
return len(tails)
```