646.md

646. Maximum Length of Pair Chain

You are given n pairs of numbers. In every pair, the first number is always smaller than the second number.

Now, we define a pair (c, d) can follow another pair (a, b) if and only if b < c. Chain of pairs can be formed in this fashion.

Given a set of pairs, find the length longest chain which can be formed. You needn't use up all the given pairs. You can select pairs in any order.

Example 1:
Input: [[1,2], [2,3], [3,4]]
Output: 2
Explanation: The longest chain is [1,2] -> [3,4]
Note:
The number of given pairs will be in the range [1, 1000].

my thoughts:

1. sort the pairs by the second number, K. check off the first pair, if later pairs has a first number smaller than K, check them off too. check the remaining first pair.
recursion implementation O(n^2) worst case.

2. a better implementation may be use a list to store the unchecked idx.

3. sort the pairs by the second number. check off the first pair, store its second number as checker. iterate the pairs, if the first num of current pair is greater than checker, update the count, move the checker to cur.second num.

my solution:

**********556ms
class Solution(object):
    def findLongestChain(self, pairs):
        """
        :type pairs: List[List[int]]
        :rtype: int
        """
        sps = sorted(pairs, key = lambda x:x[1])
        l = len(pairs)
        che = [True] * l
        def helper(sps, che, cnt, l):
            temp = None
            for i in range(l):
                if che[i]:
                    che[i] = False
                    idx = i+1
                    temp = sps[i]
                    break
            if not temp:
                return cnt
            while idx<l:
                if sps[idx][0]<=temp[1]:
                    che[idx] = False
                idx += 1
            return helper(sps, che, cnt+1, l)
        
        return helper(sps, che, 0, l)   

**********88ms
class Solution(object):
    def findLongestChain(self, pairs):
        """
        :type pairs: List[List[int]]
        :rtype: int
        """
        sps = sorted(pairs, key = lambda x:x[1])
        res = 1
        temp = sps[0][1]
        i = 1
        l = len(sps)
        while i<l:
            if sps[i][0]>temp:
                res += 1
                temp = sps[i][1]
            i += 1
        return res

my comments:

from other ppl's solution:

1. in place sort, 62 ms:
def findLongestChain(self, pairs):
        pairs.sort(key = lambda x: x[1])
        end, re = -2**31, 0
        for p in pairs:
            if p[0] > end:
                end = p[1]
                re += 1
        return re
		
2. interesting dp solution, 79ms:
class Solution(object):
    def findLongestChain(self, pairs):
        """
        :type pairs: List[List[int]]
        :rtype: int
        """
        pairs.sort(key=lambda x:x[1])
        cur_end = pairs[0][1]
        dp = [1 for i in range(len(pairs))]
        for i in range(1,len(pairs)):
            if pairs[i][0] > cur_end:
                dp[i] = dp[i-1]+1
                cur_end = pairs[i][1]
            else:
                dp[i] = dp[i-1]
        return dp[len(pairs)-1]