# Python solution with detailed explanation

• 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

``````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)
``````

• Dude, where is the detailed explanation?

• @spade what part is not explained in detail?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.