You are given N pairs of numbers. In every pair, the first number is always smaller than the second number. A pair (c, d) can follow another pair (a, b) if b < c. Chain of pairs can be formed in this fashion. You have to find the longest chain which can be formed from the given set of pairs. 
 
Example 1:
Input:
N = 5
P[] = {5  24 , 39 60 , 15 28 , 27 40 , 50 90}
Output: 3
Explanation: The given pairs are { {5, 24}, {39, 60},
{15, 28}, {27, 40}, {50, 90} },the longest chain that
can be formed is of length 3, and the chain is
{{5, 24}, {27, 40}, {50, 90}}
Example 2:
Input:
N = 2
P[] = {5 10 , 1 11}
Output: 1
Explanation:The max length chain possible is only of
length one.
 
Your Task:
You don't need to read input or print anything. Your task is to Complete the function maxChainLen() which takes a structure p[] denoting the pairs and n as the number of pairs and returns the length of the longest chain formed.
 
Expected Time Complexity: O(Nlog(N))
Expected Auxiliary Space: O(1)
Constraints:
1<=N<=10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Greedy algorithms

Starter code: #User function Template for python3



'''

class Pair(object):

    def __init__(self, a, b):

        self.a = a

        self.b = b

'''

class Solution:

    def maxChainLen(self,Parr, n):

        # Parr:  list of pair

        #code here

Solutions:
class Solution:

	def maxChainLen(self, Parr, n):
		Parr.sort(key=lambda x: x.b)
		count = 1
		i = 0
		j = 1
		while j < n:
			if Parr[i].b < Parr[j].a:
				count += 1
				i = j
			j += 1
		return count


import numpy as np

class Solution:

	def rec_sol(self, P, N, maxa):
		if N == 0:
			return 0
		temp = 0
		for i in range(N):
			if P[i].b < maxa:
				temp = max(temp, 1 + self.rec_sol(P, N - 1, P[i].a))
		return temp

	def dp_sol(self, P, N, maxa, dp):
		for i in range(N + 1):
			for j in range(maxa + 1):
				if i == 0:
					dp[i][j] = 0
				elif j == 0:
					dp[i][j] = 0
				elif P[i - 1].b < j:
					dp[i][j] = max(dp[i][j], 1 + dp[i - 1][P[i - 1].a])
		return dp[N][maxa]

	def greedy_sol(self, Parr, n):
		last = Parr.pop()
		maxa = last.a
		n = n - 1
		chain_len = 1
		while n > 0:
			n = n - 1
			curr = Parr.pop()
			curr_a = curr.a
			curr_b = curr.b
			if curr_b < maxa:
				chain_len = chain_len + 1
				maxa = curr_a
		return chain_len

	def maxChainLen(self, Parr, n):
		Parr.sort(key=lambda x: x.a)
		return self.greedy_sol(Parr, n)
		Parr.sort(key=lambda x: x.b)
		maxa = Parr[0].a
		max_ind = 0
		for i in range(1, n):
			if Parr[i].a > maxa:
				maxa = Parr[i].a
				max_ind = i
		Parr.pop(max_ind)
		return self.rec_sol(Parr, n - 1, maxa) + 1
		dp = np.array([[-1] * (maxa + 1)] * (n + 1))
		return self.dp_sol(Parr, n - 1, maxa, dp) + 1


class Solution:

	def maxChainLen(self, Parr, n):
		Parr.sort(key=lambda x: (x.a, x.b))
		ans = [Parr[0]]
		for p in Parr:
			if p.a > ans[-1].b:
				ans.append(p)
			elif p.b < ans[-1].b:
				ans[-1] = p
		return len(ans)


class Solution:

	def maxChainLen(self, Parr, n):
		l = []
		for i in range(n):
			l.append([Parr[i].a, Parr[i].b])
		l.sort()
		dp = [-1] * n

		def fun(i):
			if i == n:
				return 0
			if dp[i] != -1:
				return dp[i]
			mx = 0
			for j in range(i + 1, n):
				if l[i][1] < l[j][0]:
					mx = max(mx, fun(j))
			dp[i] = 1 + mx
			return dp[i]
		ans = 0
		k = [l[0]]
		for i in range(1, n):
			if l[i][0] > k[-1][1]:
				k.append(l[i])
			elif l[i][1] < k[-1][1]:
				k.pop(-1)
				k.append(l[i])
			else:
				continue
		ans = len(k)
		return ans


class Solution:

	def maxChainLen(self, Parr, n):
		Parr.sort(key=lambda x: x.b)
		count = 1
		prev = Parr[0].b
		for i in range(1, n):
			if prev < Parr[i].a:
				prev = Parr[i].b
				count += 1
		return count


class Solution:

	def maxChainLen(self, Parr, n):
		Parr.sort(key=lambda x: x.b)
		result = 1
		end = Parr[0].b
		for pair in Parr:
			if pair.a > end:
				result += 1
				end = pair.b
		return result


class Solution:

	def maxChainLen(self, pairs, n):
		pairs.sort(key=lambda x: x.b)
		cur = 0
		count = 0
		for pair in pairs:
			if pair.a > cur:
				cur = pair.b
				count += 1
		return count


class Solution:

	def maxChainLen(self, Parr, n):
		sortedPair = sorted(Parr, key=lambda x: x.b)
		result = 0
		prevEnd = -float('inf')
		for part in sortedPair:
			if part.a > prevEnd:
				result += 1
				prevEnd = part.b
		return result


class Solution:

	def maxChainLen(self, Parr, n):
		P = sorted(Parr, key=lambda x: x.b)
		start = P[0].b
		ans = 1
		for i in range(1, n):
			if start < P[i].a:
				ans += 1
				start = P[i].b
		return ans


class Solution:

	def maxChainLen(self, Parr, n):
		l = []
		for i in Parr:
			l.append((i.a, i.b))
		l.sort(key=lambda x: x[1])
		prev = -1000000000.0
		ans = 0
		for x in l:
			if x[0] > prev:
				ans += 1
				prev = x[1]
		return ans


class Solution:

	def maxChainLen(self, Parr, n):
		Parr.sort(key=lambda x: x.b)
		res = 1
		check = Parr[0].b
		for i in range(1, n):
			if check < Parr[i].a:
				check = Parr[i].b
				res += 1
		return res


class Solution:

	def maxChainLen(self, Parr, n):
		count = 1

		def func(x):
			return x.b
		arr = sorted(Parr, key=func)
		curr = arr[0]
		j = 0
		for i in range(len(arr) - 1):
			if curr.b < arr[i + 1].a:
				count += 1
				curr = arr[i + 1]
			else:
				j += 1
		return count


class Solution:

	def maxChainLen(self, Parr, n):
		Parr.sort(key=lambda x: x.b)
		ans = 1
		ex = Parr[0].b
		for i in range(1, n):
			if ex < Parr[i].a:
				ex = Parr[i].b
				ans += 1
		return ans


class Pair(object):

	def __init__(self, a, b):
		self.a = a
		self.b = b

class Solution:

	def maxChainLen(self, Parr, n):
		Parr.sort(key=lambda x: x.b)
		ans = 1
		(i, j) = (0, 1)
		while j < n:
			if Parr[i].b < Parr[j].a:
				ans += 1
				i = j
				j += 1
			else:
				j += 1
		return ans


class Pair(object):

	def __init__(self, a, b):
		self.a = a
		self.b = b

class Solution:

	def maxChainLen(self, Parr, n):
		Parr.sort(key=lambda x: x.b)
		ans = 1
		for i in range(1, n):
			if Parr[0].b < Parr[i].a:
				ans += 1
				Parr[0].b = Parr[i].b
		return ans


from functools import cmp_to_key

def mgc(x, y):
	if x.b > y.b:
		return 1
	elif x.b < y.b:
		return -1
	return 0

class Solution:

	def maxChainLen(self, Parr, n):
		Parr.sort(key=lambda x: x.b)
		(ans, i, j) = (0, Parr[0].b, 1)
		while j < n:
			if Parr[j].a > i:
				ans += 1
				i = Parr[j].b
				j += 1
			else:
				j += 1
		return ans + 1


class Solution:

	def maxChainLen(self, Parr, n):
		if n == 0:
			return 0

		def func(obj):
			return obj.b
		Parr.sort(key=func)
		result = []
		result.append(Parr[0])
		curr = Parr[0]
		for i in range(1, n):
			if Parr[i].a > curr.b:
				result.append(Parr[i])
				curr = Parr[i]
		return len(result)


import bisect

class Solution:

	def maxChainLen(self, prr, n):
		prr = sorted(prr, key=lambda x: (x.a, x.b))
		ar = []
		br = []
		for i in prr:
			ar.append(i.a)
		for i in prr:
			br.append(i.b)
		res = []
		res.append(prr[0])
		for i in range(1, n):
			fst = res[-1]
			if fst.b >= ar[i]:
				if br[i] < fst.b:
					res.pop(-1)
					res.append(prr[i])
			else:
				res.append(prr[i])
			i += 1
		return len(res)


class Solution:

	def maxChainLen(self, Parr, n):
		parr = Parr
		parr.sort(key=lambda x: x.b)
		c = 1
		prev = parr[0].b
		for i in range(1, n):
			if prev < parr[i].a:
				c += 1
				prev = parr[i].b
			else:
				continue
		return c


class Solution:

	def maxChainLen(self, Parr, n):
		data = [[el.a, el.b] for el in Parr]
		data.sort(key=lambda x: x[1])
		ans = 1
		prev = data[0][1]
		for i in range(1, n):
			if data[i][0] > prev:
				prev = data[i][1]
				ans += 1
		return ans


class Solution:

	def maxChainLen(self, Parr, n):
		arr = [(x.a, x.b) for x in Parr]
		arr.sort(key=lambda x: x[1])
		curr_end = arr[0][1]
		chain_len = 1
		for (start, end) in arr[1:]:
			if start > curr_end:
				curr_end = end
				chain_len += 1
		return chain_len


class Solution:

	def maxChainLen(self, Parr, n):
		list_of_elements = []
		for i in Parr:
			list_of_elements.append([i.a, i.b])
		list_of_elements = sorted(list_of_elements, key=lambda l: l[1])
		current = 1
		prev = 0
		count = 1
		while current < n:
			if list_of_elements[prev][1] < list_of_elements[current][0]:
				count += 1
				prev = current
				current += 1
			else:
				current += 1
		return count


class Solution:

	def maxChainLen(self, Parr, n):
		Parr.sort(key=lambda x: (x.b, x.a))
		l = 0
		c = 0
		for (i, x) in enumerate(Parr):
			if x.a > l:
				c += 1
				l = x.b
		return c


class Solution:

	def maxChainLen(self, Parr, n):
		Parr.sort(key=lambda pair: pair.b)
		prev = 0
		maxChain = 0
		for pair in Parr:
			if pair.a > prev:
				maxChain += 1
				prev = pair.b
		return maxChain


class Solution:

	def maxChainLen(self, Parr, n):
		arr = []
		for i in range(n):
			arr.append((Parr[i].a, Parr[i].b, i))
		arr.sort(key=lambda x: x[1])
		end_time = 0
		meeting = 0
		for x in arr:
			if end_time == 0 or end_time < x[0]:
				end_time = x[1]
				meeting += 1
		return meeting


class Solution:

	def maxChainLen(self, arr, n):
		p = []
		for i in arr:
			p.append([i.a, i.b])
		p.sort(key=lambda x: x[1])
		ans = 0
		prev = float('-inf')
		for i in p:
			if i[0] > prev:
				ans += 1
				prev = i[1]
		return ans


class Solution:

	def bisectleft(self, arr, s, e, val):
		while s < e:
			mid = (s + e) // 2
			if arr[mid].b > val:
				e = mid
			else:
				s = mid + 1
		return s

	def maxChainLen(self, Parr, n):
		Parr.sort(key=lambda x: x.b)
		length = 1
		prev = Parr[0]
		for i in range(1, n):
			if prev.b < Parr[i].a:
				prev = Parr[i]
				length += 1
		return length


class Solution:

	def maxChainLen(self, Parr, n):
		Parr.sort(key=lambda x: x.b)
		out = 1
		pre = Parr[0].b
		for i in range(1, n):
			if pre < Parr[i].a:
				pre = Parr[i].b
				out += 1
		return out


class Solution:

	def maxChainLen(self, Parr, n):
		x = [-1 for i in range(n)]
		for i in range(n):
			x[i] = [Parr[i].a, Parr[i].b]
		x = sorted(x, key=lambda sub: sub[1])
		f = 1
		i = 0
		j = 1
		while j < n:
			if x[i][1] < x[j][0]:
				f += 1
				i = j
			j += 1
		return f


class Solution:

	def maxChainLen(self, parr, n):
		ans = list()
		parr = sorted(parr, key=lambda x: x.b)
		arr = list()
		for i in range(n):
			arr.append([parr[i].a, parr[i].b])
		ans.append(arr[0])
		for i in range(1, n):
			if ans[-1][1] < arr[i][0]:
				ans.append(arr[i])
		return len(ans)


class Solution:

	def maxChainLen(self, Parr, n):
		arr = []
		for i in Parr:
			arr.append([i.a, i.b])
		arr.sort(key=lambda i: i[1])
		i = 0
		j = 1
		ans = 1
		while j < n:
			if arr[i][1] < arr[j][0]:
				ans += 1
				i = j
				j += 1
			else:
				j += 1
		return ans


class Solution:

	def maxChainLen(self, Parr, n):
		pairs = sorted(Parr, key=lambda x: x.b)
		longest_chain = 1
		prev_second = pairs[0].b
		for i in range(1, n):
			if pairs[i].a > prev_second:
				longest_chain += 1
				prev_second = pairs[i].b
		return longest_chain


class Solution:

	def maxChainLen(self, a, n):
		l = []
		for i in range(0, n):
			l.append([a[i].a, a[i].b])
		l.sort(key=lambda x: x[1])
		count = 0
		prev = -1
		for i in range(len(l)):
			if prev == -1:
				count = count + 1
				prev = l[i]
				continue
			if l[i][0] > prev[1]:
				count = count + 1
				prev = l[i]
				continue
		return count


class Solution:

	def maxChainLen(self, Parr, n):
		lst = []
		for i in Parr:
			lst.append([i.a, i.b])
		lst.sort(key=lambda x: x[1])
		c = 1
		j = 0
		for i in range(1, len(lst)):
			if lst[j][1] < lst[i][0]:
				j = i
				c = c + 1
		return c


class Solution:

	def maxChainLen(self, Parr, n):
		a1 = 0
		b1 = 0
		a2 = 0
		b2 = 0
		c = 1
		Parr.sort(key=lambda x: x.b)
		b1 = Parr[0].b
		for i in range(len(Parr) - 1):
			if b1 < Parr[i + 1].a:
				b1 = Parr[i + 1].b
				c = c + 1
		return c


class Solution:

	def maxChainLen(self, parr, n):
		parr.sort(key=lambda x: x.b)
		ans = 1
		prev = parr[0].b
		for i in range(1, n):
			if prev < parr[i].a:
				prev = parr[i].b
				ans += 1
		return ans


class Solution:

	def maxChainLen(self, Parr, n):

		def SecondElement(Pair):
			return Pair.b
		Parr.sort(key=SecondElement)
		max_length = 1
		curr_length = 1
		first = Parr[0].a
		second = Parr[0].b
		for i in range(1, len(Parr)):
			if Parr[i].a > second:
				curr_length += 1
				first = Parr[i].a
				second = Parr[i].b
			max_length = max(max_length, curr_length)
		return max_length


class Solution:

	def maxChainLen(self, Parr, n):
		Parr = sorted(Parr, key=lambda x: x.b)
		length = 1
		key = Parr[0]
		for i in range(1, n):
			if key.b < Parr[i].a:
				length += 1
				key = Parr[i]
		return length


def bs(st, a):
	(l, h) = (0, len(st) - 1)
	ind = -1
	while l <= h:
		mid = (l + h) // 2
		if st[mid] > a:
			ind = mid
			h = mid - 1
		else:
			l = mid + 1
	return ind

class Solution:

	def maxChainLen(self, arr, n):
		arr.sort(key=lambda x: x.b)
		st = []
		st.append(arr[0].b)
		for i in range(1, n):
			if arr[i].a > st[-1]:
				st.append(arr[i].b)
			else:
				ind = bs(st, arr[i].b)
				if ind != -1:
					st[ind] = arr[i].b
		return len(st)


class Solution:

	def maxChainLen(self, parr, n):
		ss = []
		for i in range(n):
			ans = [parr[i].a, parr[i].b]
			ss.append(ans)
		ss.sort(key=lambda x: x[1])
		li = []
		for i in ss:
			if li and li[-1][1] < i[0]:
				li.append(i)
			if not li:
				li.append(i)
		return len(li)


from bisect import bisect_right as upper
import sys

class Solution:

	def maxChainLen(self, arr, n):
		arr.sort(key=lambda x: x.b)
		ans = 1
		prevend = arr[0].b
		for i in range(1, n):
			if arr[i].a > prevend:
				ans += 1
				prevend = arr[i].b
		return ans


class Solution:

	def maxChainLen(self, Parr, n):
		arr = [(Parr[i].a, Parr[i].b) for i in range(n)]
		arr.sort(key=lambda x: x[1])
		time = -1
		count = 0
		for (start, end) in arr:
			if time < start:
				count += 1
				time = end
		return count


class Solution:

	def maxChainLen(self, Parr, n):
		Parr = sorted(Parr, key=lambda x: x.b)
		first = Parr[0]
		i = 0
		count = 1
		while i < n:
			if first.b < Parr[i].a:
				count += 1
				first = Parr[i]
			i += 1
		return count


class Solution:

	def maxChainLen(self, Parr, n):
		parr = sorted(Parr, key=lambda x: x.b)
		dp = [1 for i in range(n + 1)]
		prev = parr[0].b
		ans = 1
		for i in range(1, n):
			(a, b) = (parr[i].a, parr[i].b)
			if a > prev:
				dp[i] = dp[i - 1] + 1
				ans = ans + 1
				prev = b
		return ans


class Solution:

	def maxChainLen(self, parr, n):
		l = []
		for i in range(n):
			l.append([parr[i].b, parr[i].a])
		l.sort()
		ans = 1
		val = l[0][0]
		for i in range(1, n):
			if l[i][1] > val:
				val = l[i][0]
				ans = ans + 1
		return ans


class Solution:

	def maxChainLen(self, Parr, n):
		Parr.sort(key=lambda x: (x.b, x.a))
		ans = 0
		last = float('-inf')
		for p in Parr:
			if p.a > last:
				ans += 1
				last = p.b
		return ans


def solver(pairs, i, n, dct):
	if i in dct:
		return dct[i]
	sm = 0
	for j in range(i + 1, n):
		if pairs[j][0] > pairs[i][1]:
			sm = max(sm, solver(pairs, j, n, dct) + 1)
		else:
			sm = max(sm, solver(pairs, j, n, dct))
	dct[i] = sm
	return sm

class Solution:

	def maxChainLen(self, Parr, n):
		dct = dict()
		dct1 = dict()
		for i in Parr:
			if i.a in dct1:
				dct1[i.a] = min(i.b, dct1[i.a])
			else:
				dct1[i.a] = i.b
		new = [[i, dct1[i]] for i in dct1]
		new.sort(key=lambda x: x[0])
		ans = 1
		curr = len(new) - 1
		curr_cmp = new[curr][0]
		for i in range(len(new) - 2, -1, -1):
			if new[i][1] < curr_cmp:
				curr_cmp = new[i][0]
				ans += 1
		return ans
		return solver(new, 0, len(new), dct) + 1


class Solution:

	def maxChainLen(self, Parr, n):

		def abc(x):
			return x[1]
		ans = [[i.a, i.b] for i in Parr]
		ans = sorted(ans, key=abc)
		c = 1
		i = 1
		x = ans[0][1]
		while i < n:
			if ans[i][0] > x:
				c += 1
				x = ans[i][1]
			i += 1
		return c


class Solution:

	def maxChainLen(self, Parr, n):
		Parr = sorted(Parr, key=lambda x: x.b)
		First = Parr[0]
		count = 1
		for i in range(1, len(Parr)):
			if First.b < Parr[i].a:
				count += 1
				First = Parr[i]
		return count


class Solution:

	def maxChainLen(self, arr, n):
		dp = [1 for i in range(n)]
		arr.sort(key=lambda x: x.b)
		ans = 0
		mi = -1
		for i in range(len(arr)):
			if arr[i].a > mi:
				mi = arr[i].b
				ans += 1
		return ans


class Solution:

	def maxChainLen(self, Parr, n):
		sorted_pair_list = sorted(Parr, key=lambda x: x.a)
		final_list = []
		if sorted_pair_list:
			final_list.append(sorted_pair_list[0])
			if len(sorted_pair_list) > 1:
				for idx in range(1, len(sorted_pair_list)):
					if final_list[-1].b < sorted_pair_list[idx].a:
						final_list.append(sorted_pair_list[idx])
					elif final_list[-1].b > sorted_pair_list[idx].b:
						final_list.pop()
						final_list.append(sorted_pair_list[idx])
		return len(final_list)


class Solution:

	def maxChainLen(self, p, n):
		arr = [[obj.a, obj.b] for obj in p]
		arr.sort(key=lambda x: x[1])
		prev = arr[0][1]
		curr = 1
		for i in range(1, n):
			if arr[i][0] > prev:
				prev = arr[i][1]
				curr += 1
		return curr


class Solution:

	def maxChainLen(self, Parr, n):
		pairs = sorted(Parr, key=lambda p: p.b)
		ans = 0
		p = float('-inf')
		for c in pairs:
			if c.a > p:
				ans += 1
				p = c.b
		return ans


from functools import cmp_to_key

class Solution:

	def comparator(x, y):
		return x.b - y.b

	def maxChainLen(self, Parr, n):
		Parr = sorted(Parr, key=cmp_to_key(Solution.comparator))
		prev = float('-inf')
		cnt = 0
		for i in Parr:
			if prev < i.a:
				cnt += 1
				prev = i.b
		return cnt


class Solution:

	def maxChainLen(self, parr, n):
		parr.sort(key=lambda x: x.b)
		prev_num = parr[0].b
		sz = 1
		for i in range(1, len(parr)):
			if prev_num < parr[i].a:
				sz += 1
				prev_num = parr[i].b
		return sz


class Solution:

	def maxChainLen(self, Parr, n):
		arr = []
		for i in range(n):
			arr.append([Parr[i].a, Parr[i].b])
		new_arr = sorted(arr, key=lambda x: x[0], reverse=True)
		count = 1
		c = new_arr[0][0]
		for i in range(1, n):
			if c > new_arr[i][1]:
				count += 1
				c = new_arr[i][0]
		return count


class Solution:

	def maxChainLen(self, Parr, n):
		arr = []
		for i in Parr:
			arr.append((i.a, i.b))
		arr.sort(key=lambda x: x[1])
		currMeet = 0
		nextMeet = 1
		ans = 1
		while nextMeet < n:
			if arr[currMeet][1] < arr[nextMeet][0]:
				ans += 1
				currMeet = nextMeet
			nextMeet += 1
		return ans