Note: This POTD is a part of Geek Summer Carnival. Solve all POTD consecutively from 5th to 10th April and get a chance to win exclusive discount vouchers on our GfG courses.
Geek wants to select the maximum number of course bundles at the Geek Summer Carnival. 
You are given a finite number of courses and N range of numbers each depicting a bundle of courses. Select the maximum number of bundles such that no courses overlap in any of the bundle.
Note: The ending of a range being the same as start of another isn't considered as an overlap.
Example 1:
Input:
N = 4
Bundles = 
1 5
2 3
1 8
3 5
Output:
2
Explanation: 
We can select 2 bundles at max while 
staying true to the condition. For this, 
we can pick the ranges (2,3) and (3,5) 
without any overlap. 
 
Example 2:
Input:
N = 5
Bundles = 
7 9 
2 8 
1 3 
10 11 
10 16
Output:
3
Explanation: 
We can pick the ranges (1,3), 
(7,9) and (10,11) without any overlap.
Your Task:
You don't need to read input or print anything. Complete the function max_non_overlapping() that takes a 2D array representing N ranges as input parameter.  Return the maximum number of course bundles. 
Expected time complexity: O(NlogN)
Expected space complexity: O(1)
Constraints:
1 <= N <= 1000
0 <= range[i][j] <= 1000

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Starter code: # ranges[i][0] is the start of ith range

# ranges[i][1] is the end of ith range



class Solution:

        

    def max_non_overlapping(self,ranges):

        # code here

Solutions:
class Solution:

	def max_non_overlapping(self, ranges):
		ranges.sort(key=lambda x: (x[1], x[0]))
		ans = 0
		prev = -1
		for r in ranges:
			if r[0] >= prev:
				ans += 1
				prev = r[1]
		return ans


class Solution:

	def max_non_overlapping(self, ranges):
		count = 1
		ranges.sort(key=lambda x: (x[1], x[0]))
		end = ranges[0][1]
		for i in range(1, n):
			if ranges[i][0] >= end:
				count += 1
				end = ranges[i][1]
		return count


class Solution:

	def max_non_overlapping(self, ranges):
		ranges.sort()
		s = []
		for (start, end) in ranges:
			while s and s[-1] > end:
				s.pop()
			if not s or start >= s[-1]:
				s.append(end)
		return len(s)


class Solution:

	def max_non_overlapping(self, ranges):
		count = 0
		ranges.sort(key=lambda x: x[1])
		prev = -1
		for i in ranges:
			(st, ed) = i
			if st >= prev:
				prev = ed
				count += 1
		return count


class Solution:

	def max_non_overlapping(self, ranges):
		ranges.sort(key=lambda x: x[1])
		count = 0
		time = 0
		for (start, end) in ranges:
			if time <= start:
				count += 1
				time = end
		return count


class Solution:

	def max_non_overlapping(self, ranges):
		ranges.sort(key=lambda x: x[1])
		currend = ranges[0][1]
		m = 1
		for i in range(1, len(ranges)):
			if ranges[i][0] >= currend:
				m += 1
				currend = ranges[i][1]
		return m


class Solution:

	def max_non_overlapping(self, arr):
		arr.sort(key=lambda x: x[1])
		arr.sort(key=lambda x: x[0])
		ans = []
		for (i, j) in arr:
			while ans and ans[-1] > j:
				ans.pop()
			if not ans or i >= ans[-1]:
				ans.append(j)
		return len(ans)


class Solution:

	def max_non_overlapping(self, ranges):
		ranges = sorted(ranges, key=lambda x: x[1])
		b = 1
		a = ranges[0]
		for i in range(1, len(ranges)):
			if ranges[i][0] >= a[1]:
				b += 1
				a = ranges[i]
		return b


class Solution:

	def max_non_overlapping(self, ranges):
		r = sorted(ranges, key=lambda x: x[1])
		count = 1
		en = r[0][1]
		for i in range(1, len(r)):
			if r[i][0] >= en:
				count = count + 1
				en = r[i][1]
		return count


class Solution:

	def max_non_overlapping(self, ranges):
		ranges.sort(key=lambda x: x[1])
		ans = 0
		last = -1
		for i in ranges:
			if i[0] >= last:
				last = i[1]
				ans += 1
		return ans


class Solution:

	def max_non_overlapping(self, ranges):
		result = 1
		r = sorted(ranges, key=lambda x: x[1])
		prev = r[0]
		for i in range(1, len(r)):
			if r[i][0] >= prev[1]:
				result = result + 1
				prev = r[i]
		return result


class Solution:

	def max_non_overlapping(self, ranges):
		ranges.sort(key=lambda x: x[1])
		count = 1
		ending = ranges[0][1]
		for pair in ranges[1:]:
			if pair[0] >= ending:
				count = count + 1
				ending = pair[1]
		return count


class Solution:

	def max_non_overlapping(self, ranges):
		ranges.sort()
		total_count = 0
		current_range = None
		for range in ranges:
			if current_range == None:
				current_range = range
				total_count += 1
			elif range[0] > current_range[0] and range[1] < current_range[1]:
				current_range = range
			elif range[0] >= current_range[1]:
				current_range = range
				total_count += 1
		return total_count


class Solution:

	def max_non_overlapping(self, ranges):
		ranges.sort(key=lambda x: x[1])
		m = ranges[0][1]
		count = 1
		for i in range(1, n):
			if m <= ranges[i][0]:
				m = ranges[i][1]
				count += 1
			else:
				continue
		return count


class Solution:

	def max_non_overlapping(self, ranges):
		ranges.sort()
		s = []
		for (i, j) in ranges:
			while s and s[-1] > j:
				s.pop()
			if not s or i >= s[-1]:
				s.append(j)
		return len(s)


class Solution:

	def max_non_overlapping(self, arr):
		n = len(arr)
		arr.sort(key=lambda x: x[1])
		ans = 1
		curr = 0
		for i in range(1, n):
			if arr[i][0] >= arr[curr][1]:
				ans += 1
				curr = i
		return ans


class Solution:

	def max_non_overlapping(self, ranges):
		h = {}
		ranges.sort(key=lambda x: x[1])
		temp = [-1, -1]
		count = 0
		for i in range(0, len(ranges)):
			if ranges[i][0] >= temp[1]:
				count += 1
				temp = ranges[i]
		return count


class Solution:

	def max_non_overlapping(self, ranges):
		ranges.sort(key=lambda x: x[1])
		courses = []
		for (strt, end) in ranges:
			if not courses or strt >= courses[-1][1]:
				courses.append([strt, end])
		return len(courses)


class Solution:

	def max_non_overlapping(self, ranges):
		ranges = sorted(ranges, key=lambda x: [x[1], -x[0]])
		(count, rear) = (0, 0)
		for (st, ed) in ranges:
			if rear <= st:
				count += 1
				rear = ed
		return count


class Solution:

	def max_non_overlapping(self, ranges):
		ranges = sorted(ranges, key=lambda x: x[1])
		cnt = 1
		start = ranges[0]
		for i in range(1, len(ranges)):
			if ranges[i][0] >= start[1]:
				cnt += 1
				start = ranges[i]
		return cnt


class Solution:

	def max_non_overlapping(self, r):
		r.sort(key=lambda x: x[1])
		a = -1
		c = 0
		for i in r:
			if i[0] >= a:
				a = i[1]
				c += 1
		return c


class Solution:

	def max_non_overlapping(self, ranges: list):
		ranges.sort(key=lambda r: r[1])
		(ans, lst) = (1, ranges[0])
		for i in range(1, len(ranges)):
			(l1, r1) = lst
			(l2, r2) = ranges[i]
			if r1 <= l2:
				ans += 1
				lst = ranges[i]
		return ans


class Solution:

	def max_non_overlapping(self, ranges):
		ranges.sort(key=lambda x: x[1])
		ma = 0
		le = len(ranges)
		cnt = 0
		for i in range(le):
			if ranges[i][0] >= ma:
				ma = ranges[i][1]
				cnt += 1
		return cnt


class Solution:

	def max_non_overlapping(self, ranges):
		from collections import deque
		ranges.sort(key=lambda x: (x[1], -x[0]))
		ans = 1
		prev = ranges[0][1]
		for i in range(1, len(ranges)):
			if ranges[i][0] >= prev:
				ans += 1
				prev = ranges[i][1]
		return ans


class Solution:

	def max_non_overlapping(self, ranges):
		ranges.sort()
		ans = 1
		end = ranges[0][1]
		for i in range(len(ranges)):
			if ranges[i][0] < end:
				end = min(end, ranges[i][1])
			else:
				ans += 1
				end = ranges[i][1]
		return ans


class Solution:

	def max_non_overlapping(self, ranges):
		ranges.sort(key=lambda x: x[1])
		ans = 1
		prev = ranges[0]
		for i in range(1, len(ranges)):
			if ranges[i][0] >= prev[1]:
				ans += 1
				prev = ranges[i]
		return ans


class Solution:

	def max_non_overlapping(self, ranges):
		c = 0
		ranges.sort(key=lambda x: x[1])
		ve = -1000000
		for i in ranges:
			cs = i[0]
			ce = i[1]
			if cs >= ve:
				c += 1
				ve = ce
		return c


from bisect import bisect_left as bl

class Solution:

	def max_non_overlapping(self, ranges):
		ranges = sorted(ranges)
		dummys = [r[0] for r in ranges]
		min_i = ranges[0][0]
		max_i = ranges[-1][0]
		memo = [0 for _ in range(min_i, max_i + 1)]
		memo[-1] = 1
		for i in range(max_i - 1 - min_i, -1, -1):
			memo[i] = memo[i + 1]
			j = bl(dummys, i + min_i)
			while j < len(ranges) and ranges[j][0] == i + min_i:
				end = ranges[j][1] - min_i
				post = 0 if end >= len(memo) else memo[end]
				memo[i] = max(memo[i], 1 + post)
				j += 1
		return memo[0]


class Solution:

	def max_non_overlapping(self, ranges):
		ranges.sort(key=lambda x: x[1])
		end = -1
		c = 0
		for i in ranges:
			if end <= i[0]:
				c += 1
				end = i[1]
		return c


class Solution:

	def max_non_overlapping(self, ranges):
		ranges = sorted(ranges, key=lambda x: x[1])
		nxt = 1
		pre = ranges[0]
		for i in range(1, len(ranges)):
			if ranges[i][0] >= pre[1]:
				nxt += 1
				pre = ranges[i]
		return nxt


class Solution:

	def max_non_overlapping(self, ranges):
		ranges.sort(key=lambda x: x[1])
		ans = 0
		cur = 0
		for i in range(n):
			if ranges[i][0] >= cur:
				ans += 1
				cur = ranges[i][1]
		return ans


class Solution:

	def max_non_overlapping(self, ranges):
		ranges.sort(key=lambda a: a[1])
		last = ranges[0][0]
		count = 0
		for i in ranges:
			if i[0] >= last:
				count += 1
				last = i[1]
		return count


class Solution:

	def max_non_overlapping(self, ranges):
		ranges.sort(key=lambda x: x[1])
		st = ranges[0][0]
		en = ranges[0][1]
		i = 1
		ct = 1
		while i < len(ranges):
			if ranges[i][0] >= en and ranges[i][0] > st:
				st = ranges[i][0]
				en = ranges[i][1]
				ct += 1
			i += 1
		return ct


import sys

class Solution:

	def max_non_overlapping(self, ranges):
		count = 0
		curr_max = -1
		ranges = sorted(ranges, key=lambda x: x[1])
		for i in ranges:
			if i[0] >= curr_max and i[1] > curr_max:
				count += 1
				curr_max = i[1]
		return count


class Solution:

	def max_non_overlapping(self, ranges):
		n = len(ranges)
		if n <= 1:
			return n
		ranges.sort(key=lambda ranges: ranges[0])
		end = ranges[0][1]
		max = 1
		for i in range(n):
			if ranges[i][0] < end:
				end = min(end, ranges[i][1])
			else:
				max += 1
				end = ranges[i][1]
		return max


from operator import itemgetter

class Solution:

	def max_non_overlapping(self, ranges):
		ranges.sort(key=lambda x: x[1])
		(pL, pR) = ranges[0]
		count = 1
		for i in range(1, len(ranges)):
			(nL, nR) = ranges[i]
			if nL >= pR:
				(pL, pR) = ranges[i]
				count += 1
		return count


class Solution:

	def max_non_overlapping(self, ranges):
		ranges.sort(key=lambda a: a[1])
		(c, end) = (0, -1)
		for num in ranges:
			if end <= num[0]:
				c += 1
				end = num[1]
		return c


class Solution:

	def max_non_overlapping(self, ranges):
		ranges.sort(key=lambda x: x[1])
		max_count = 0
		prev = -1
		for j in range(n):
			if prev <= ranges[j][0]:
				max_count += 1
				prev = ranges[j][1]
		return max_count


class Solution:

	def max_non_overlapping(self, events):
		events.sort(key=lambda event: event[1])
		prev = -1
		count = 0
		for i in range(n):
			if events[i][0] >= prev:
				count += 1
				prev = events[i][1]
		return count