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].

Difficulty: interview

Starter code:

class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        

Solutions:
class Solution:
     def findLongestChain(self, pairs):
         """
         :type pairs: List[List[int]]
         :rtype: int
         """
         pairs = sorted(pairs,key=lambda x:x[1])
         res = 1
         first = pairs[0]
         for i in pairs[1:]:
             if first[-1] < i[0]:
                 res += 1
                 first = i
         return res


class Solution:
     def findLongestChain(self, pairs):
         """
         :type pairs: List[List[int]]
         :rtype: int
         """
         cur, res = float('-inf'), 0
         for x, y in sorted(pairs, key=operator.itemgetter(1)):
             if cur < x:
                 cur = y
                 res += 1
         return res


class Solution:
     def findLongestChain(self, pairs):
         """
         :type pairs: List[List[int]]
         :rtype: int
         """
         # pairs = sorted(pairs, key=lambda x: x[0]) # 动态规划, 居然也超时了
         # dp = [1] * len(pairs)
         # for i in range(len(pairs)):
         #     for j in range(i):
         #         if pairs[j][1] < pairs[i][0]:
         #             dp[i] = max(dp[i], dp[j]+1)
         # return max(dp)
         
         pairs.sort(key=lambda x: x[1])
         cur = pairs[0][0] - 1
         ans = 0
         for a, b in pairs:
             if cur < a:
                 cur = b
                 ans += 1
         return ans


class Solution:
     def findLongestChain(self, pairs):
         """
         :type pairs: List[List[int]]
         :rtype: int
         """
         if not pairs:
             return 0
         
         pairs.sort(key= lambda x: x[1])        
         size = 1
         prev = pairs[0]
         
         for p in pairs[1:]:
             if prev[1] < p[0]:
                 size += 1
                 prev = p
         return size

class Solution:
     def findLongestChain(self, pairs):
         """
         :type pairs: List[List[int]]
         :rtype: int
         """
         pairs = sorted([tuple(x) for x in pairs], key=lambda i: i[1])
         current, count = -0x3f3f3f3f, 0
         for a, b in pairs:
             if a > current:
                 current = b
                 count += 1
         return count


class Solution:
     def findLongestChain(self, pairs):
         """
         :type pairs: List[List[int]]
         :rtype: int
         """
         pairs=sorted(pairs,key=lambda t:t[0])
         p,L=None,0
         for t in sorted(pairs,key=lambda t:t[1]):
             if p is None or t[0]>p: p,L=t[1],L+1
         return L

import operator
 class Solution:
     def findLongestChain(self, pairs):
         """
         :type pairs: List[List[int]]
         :rtype: int
         """
         pairs.sort(key=operator.itemgetter(1, 0))
         maxNum = -float('inf')
         ret = 0
         for pair in pairs:
             if pair[0] > maxNum:
                 maxNum = pair[1]
                 ret += 1
         return ret

class Solution(object):
     def findLongestChain(self, pairs):
 
         pairs = sorted(pairs, key = lambda x:x[1])
 
         count = 1
         curr = pairs[0]
         for pair in pairs:
             if curr[1] < pair[0]:
                 count += 1
                 curr = pair
         return count

class Solution:
     def findLongestChain(self, pairs):
         """
         :type pairs: List[List[int]]
         :rtype: int
         """
         queue = collections.deque(sorted(pairs, key=lambda pair: pair[1]))
         
         count = 0
         
         while len(queue) > 0:
           count += 1
           curr = queue.popleft()
           while len(queue) > 0 and queue[0][0] <= curr[1]:
             queue.popleft()
         
         return count