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

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Sorting

Data structures

Greedy algorithms

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

Solutions:
class Solution:

	def findLongestChain(self, pairs):
		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):
		(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):
		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):
		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):
		pairs = sorted([tuple(x) for x in pairs], key=lambda i: i[1])
		(current, count) = (-1061109567, 0)
		for (a, b) in pairs:
			if a > current:
				current = b
				count += 1
		return count


class Solution:

	def findLongestChain(self, pairs):
		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


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