Given a list intervals of n intervals, the ith element [s, e, p] denotes the starting point s, ending point e, and the profit p earned by choosing the ith interval. Find the maximum profit one can achieve by choosing a subset of non-overlapping intervals.
Two intervals [s1, e1, p1] and [s2, e2, p2] are said to be non-overlapping if [e1 <= s2] and [s1 < s2].
Example 1:
Input:
n = 3
intervals = {
{1, 2, 4},
{1, 5, 7},
{2, 4, 4}
}
Output:
8
Explanation:
One can choose intervals [1, 2, 4] and [2, 4, 4] for a 
profit of 8.
Example 2:
Input:
n = 3
intervals = {
{1, 4, 4},
{2, 3, 7},
{2, 3, 4}
}
Output:
7
Explanation:
One can choose interval [2, 3, 7] for a profit of 7.
Your Task:
You don't need to print or output anything. Complete the function maximum_profit() which takes an integer n and a 2D integer array intervals and returns an integer, denoting the maximum profit which one can get by choosing the non-overlapping intervals.
Constraints:
	1 <= n and n <= 10^{4}
	1 <= starting point of ith interval < ending point of ith interval <= 10^{5}
	1 <= profit earned by choosing ith interval <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: from typing import List





class Solution:

    def maximum_profit(self, n : int, intervals : List[List[int]]) -> int:

        # code here

        



Solutions:
from typing import List

class Solution:

	def maximum_profit(self, n: int, intervals: List[List[int]]) -> int:
		intervals.sort(key=lambda x: (x[1], x[0]))
		M = intervals[-1][1]
		dp = [0] * (M + 1)
		for i in range(n):
			(s, e, p) = intervals[i]
			if p + dp[s] > dp[e]:
				dp[e] = p + dp[s]
			if i < n - 1:
				(_, en, _) = intervals[i + 1]
				for j in range(e + 1, en + 1):
					dp[j] = dp[e]
		return dp[M]


from typing import List
from collections import deque

class Solution:

	def maximum_profit(self, n: int, intervals: List[List[int]]) -> int:

		def getNext(node):
			l = 0
			r = n - 1
			ans = n
			while l <= r:
				mid = (l + r) // 2
				if intervals[mid][0] < intervals[node][1]:
					l = mid + 1
				else:
					r = mid - 1
					ans = min(ans, mid)
			return ans
		intervals.sort()
		dp = [0 for _ in intervals]
		for i in range(n - 1, -1, -1):
			next_i = getNext(i)
			if next_i >= n:
				dp[i] = intervals[i][2]
			else:
				dp[i] = intervals[i][2] + dp[next_i]
			if i != n - 1:
				dp[i] = max(dp[i], dp[i + 1])
		return dp[0]


from typing import List
import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def maximum_profit(self, n: int, intervals: List[List[int]]) -> int:
		intervals = sorted(intervals, key=lambda x: x[0])

		def binary(intervals, i, cur_ed):
			st = i + 1
			ed = len(intervals) - 1
			ans = -1
			while st <= ed:
				mid = (st + ed) // 2
				if intervals[mid][0] < cur_ed:
					st = mid + 1
				else:
					ans = mid
					ed = mid - 1
			return ans
		dp = [0 for i in range(n)]
		dp[-1] = intervals[-1][2]
		for i in range(n - 2, -1, -1):
			cur_ed = intervals[i][1]
			dp[i] = intervals[i][2]
			idx = binary(intervals, i, cur_ed)
			if idx >= 0:
				dp[i] += dp[idx]
			dp[i] = max(dp[i], dp[i + 1])
		return dp[0]


from typing import List
from bisect import bisect_left as lower
import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def maximum_profit(self, n: int, arr: List[List[int]]) -> int:
		arr.sort()
		marr = [0] * n
		for i in range(0, n):
			marr[i] = arr[i][0]

		def solve(i):
			if i == n:
				return 0
			if dp[i] != 0:
				return dp[i]
			nextidx = lower(marr, arr[i][1])
			include = arr[i][2] + solve(nextidx)
			exclude = solve(i + 1)
			dp[i] = max(include, exclude)
			return dp[i]
		dp = [0 for i in range(0, n)]
		return solve(0)


from typing import List
import sys
sys.setrecursionlimit(100000)

class Solution:

	def find_next_index(self, index, intervals):
		left = index + 1
		right = len(intervals) - 1
		current_value = intervals[index][1]
		ans = -1
		while left <= right:
			ms = (left + right) // 2
			if current_value <= intervals[ms][0]:
				ans = ms
				right = ms - 1
			else:
				left = ms + 1
		return ans

	def find_profits(self, index, intervals, memorize):
		if index >= len(intervals):
			return 0
		if memorize[index] != -1:
			return memorize[index]
		else:
			skip = self.find_profits(index + 1, intervals, memorize)
			next_index = self.find_next_index(index, intervals)
			profit = intervals[index][2]
			if next_index != -1:
				profit += self.find_profits(next_index, intervals, memorize)
			memorize[index] = max(skip, profit)
			return memorize[index]

	def maximum_profit(self, n: int, intervals: List[List[int]]) -> int:
		memorize = [-1] * (n + 1)
		intervals.sort()
		return self.find_profits(0, intervals, memorize)


from bisect import bisect

class Solution:

	def maximum_profit(self, n, A):
		A.sort(key=lambda x: x[1:])
		D = [0]
		P = [0]
		for (s, e, p) in A:
			i = bisect(D, s) - 1
			c = P[i] + p
			if c <= P[-1]:
				continue
			D.append(e)
			P.append(c)
		return P[-1]


from typing import List
import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def bs(self, tgt, arr, n):
		hi = n
		lo = 0
		ans = -1
		while lo < hi:
			mid = (hi + lo) // 2
			if arr[mid][0] < tgt:
				lo = mid + 1
			else:
				ans = mid
				hi = mid
		return ans

	def fun(self, index, arr, n, visited):
		if index >= n:
			return (0, visited)
		if visited[index] > -1:
			return (visited[index], visited)
		take = arr[index][2]
		ind = self.bs(arr[index][1], arr, n)
		if ind >= 0:
			(tak, visited) = self.fun(ind, arr, n, visited)
			take += tak
		(skip, visited) = self.fun(index + 1, arr, n, visited)
		visited[index] = max(skip, take)
		return (max(skip, take), visited)

	def maximum_profit(self, n: int, intervals: List[List[int]]) -> int:
		intervals.sort()
		arr = [-1] * n
		return self.fun(0, intervals, n, arr)[0]


from typing import List
from bisect import bisect_left

class Solution:

	def maximum_profit(self, n: int, intervals: List[List[int]]) -> int:
		profits = [0] * (n + 1)
		intervals.sort(key=lambda l: l[0])
		start_list = [l[0] for l in intervals]
		for i in range(len(intervals) - 1, -1, -1):
			(start, end, profit) = intervals[i]
			j = bisect_left(start_list, end, lo=i + 1)
			next_int_pft = profits[j] if j < n else 0
			profits[i] = max(profit + next_int_pft, profits[i + 1])
		return profits[0]


from typing import List

class Solution:

	def maximum_profit(self, n: int, intervals: List[List[int]]) -> int:
		sorted_intervals = sorted(intervals, key=lambda x: x[1])
		ans = [0 for i in range(n)]
		ans[0] = sorted_intervals[0][-1]
		for i in range(1, n):
			(start, end, profit) = sorted_intervals[i]
			if sorted_intervals[0][1] > start:
				ans[i] = max(ans[i - 1], profit)
			else:
				l = 0
				r = i - 1
				while l < r:
					mid = (l + r) // 2
					if sorted_intervals[mid][1] > start:
						r = mid
					else:
						l = mid + 1
				if sorted_intervals[r][1] > start:
					r -= 1
				ans[i] = max(ans[i - 1], ans[r] + profit)
		return ans[-1]


from typing import List

class Solution:

	def maximum_profit(self, n: int, intervals: List[List[int]]) -> int:

		def bs(intervals, x, l, r):
			ind = -1
			while l <= r:
				mid = l + (r - l) // 2
				if x <= intervals[mid][0]:
					ind = mid
					r = mid - 1
				else:
					l = mid + 1
			return ind
		intervals.sort()
		dp = [0] * n
		for i in range(n - 1, -1, -1):
			ind = bs(intervals, intervals[i][1], i + 1, n - 1)
			if ind == -1:
				dp[i] += intervals[i][2]
			else:
				dp[i] += intervals[i][2] + dp[ind]
			if i != n - 1:
				dp[i] = max(dp[i], dp[i + 1])
		return dp[0]


from typing import List

def binary_search(i, arr, n, ele):
	i = i
	j = n - 1
	while i <= j:
		mid = (i + j) // 2
		if ele == arr[mid][0]:
			return mid
		elif ele > arr[mid][0]:
			i = mid + 1
		elif ele < arr[mid][0]:
			j = mid - 1
	return i

def solveBs(i, arr, n):
	if i > n - 1:
		return 0
	take = arr[i][2] + solveBs(binary_search(i + 1, arr, n, arr[i][1]), arr, n)
	nottake = solveBs(i + 1, arr, n)
	return max(take, nottake)

def sovleBsTabulation(arr, n, dp):
	for i in range(n - 1, -1, -1):
		take = arr[i][2] + dp[binary_search(i + 1, arr, n, arr[i][1])]
		nottake = dp[i + 1]
		dp[i] = max(take, nottake)

class Solution:

	def maximum_profit(self, n: int, arr: List[List[int]]) -> int:
		n = len(arr)
		arr = list(sorted(arr, key=lambda x: x[0]))
		dp = [0 for i in range(n + 1)]
		res = sovleBsTabulation(arr, n, dp)
		return dp[0]


from typing import List

class Solution:

	def binary_search(self, dp, start, end, target):
		while start < end:
			mid = (start + end) // 2
			if dp[mid][0] == target:
				return mid
			elif dp[mid][0] > target:
				end = mid
			else:
				start = mid + 1
		if dp[start][0] > target:
			start -= 1
		return start

	def maximum_profit(self, n: int, intervals: List[List[int]]) -> int:
		n = len(intervals)
		ind = 0
		intervals.sort(key=lambda x: x[1])
		dp = [[0, 0] for i in range(n + 1)]
		for i in range(n):
			loc = self.binary_search(dp, 0, ind, intervals[i][0])
			if dp[ind][0] < intervals[i][1]:
				ind += 1
				dp[ind][0] = intervals[i][1]
			dp[ind][1] = max(dp[ind][1], dp[ind - 1][1])
			dp[ind][1] = max(dp[ind][1], dp[loc][1] + intervals[i][2])
		return dp[ind][1]


from typing import List

class Solution:

	def binarySearch(ans, temp, start, i):
		(l, r) = (0, i - 1)
		idx = -1
		while l <= r:
			mid = (l + r) // 2
			if temp[mid][1] <= start:
				idx = mid
				l = mid + 1
			else:
				r = mid - 1
		if idx == -1:
			return 0
		return max(ans[idx][0], ans[idx][1])

	def maximum_profit(self, n: int, intervals: List[List[int]]) -> int:
		temp = intervals.copy()
		temp.sort(key=lambda x: x[1])
		ans = [[temp[0][2], 0]]
		for i in range(1, n):
			j = i - 1
			pro1 = Solution.binarySearch(ans, temp, temp[i][0], i) + temp[i][2]
			pro2 = max(ans[i - 1][0], ans[i - 1][1])
			ans.append([pro1, pro2])
		return max(ans[-1][0], ans[-1][1])


from typing import List

class Solution:

	def binary_search(self, arr, end_time):
		l = 0
		ans = len(arr)
		h = len(arr) - 1
		while l <= h:
			mid = (l + h) // 2
			if arr[mid][0] < end_time:
				l = mid + 1
			else:
				h = mid - 1
				ans = min(ans, mid)
		return ans

	def maximum_profit(self, n: int, intervals: List[List[int]]) -> int:
		intervals.sort(key=lambda x: x[0])
		dp = [0] * n
		for i in range(n - 1, -1, -1):
			new_i = self.binary_search(intervals, intervals[i][1])
			if new_i >= n:
				dp[i] = intervals[i][2]
			else:
				dp[i] = intervals[i][2] + dp[new_i]
			if i != n - 1:
				dp[i] = max(dp[i], dp[i + 1])
		return dp[0]


from typing import List
from time import time

class Interval:

	def __init__(self, data) -> None:
		self.start_idx = data[0]
		self.end_idx = data[1]
		self.profit = data[2]

class Solution:

	def find_non_conflicting_interval(self, n: int, intervals: List[Interval], item: Interval):
		low = 0
		high = n - 1
		ans_idx = n
		while low <= high:
			mid = low + (high - low) // 2
			if intervals[mid].start_idx < item.end_idx:
				low = mid + 1
			else:
				high = mid - 1
				ans_idx = min(ans_idx, mid)
		return ans_idx

	def maximum_profit(self, n: int, intervals: List[List[int]]):
		if n == 0:
			return 0
		if n == 1:
			return intervals[0][2]
		intervals_arr = list()
		for i in range(len(intervals)):
			intervals_arr.append(Interval(intervals[i]))
		intervals_arr.sort(key=lambda x: (x.start_idx, x.end_idx))
		dp = [0] * n
		for i in range(n - 1, -1, -1):
			idx = self.find_non_conflicting_interval(n, intervals_arr, intervals_arr[i])
			if idx >= n:
				dp[i] = intervals_arr[i].profit
			else:
				dp[i] = intervals_arr[i].profit + dp[idx]
			if i != n - 1:
				dp[i] = max(dp[i], dp[i + 1])
		return dp[0]


from typing import List
import bisect

class Solution:

	def maximum_profit(self, n: int, intervals: List[List[int]]) -> int:
		intervals.sort()
		memo = {}
		memo[n] = 0
		maxProfit = 0
		for i in range(n)[::-1]:
			(s, e, p) = intervals[i]
			if i == n - 1:
				memo[i] = p
				maxProfit = p
				continue
			next = bisect.bisect_left(KeyList(intervals, key=lambda x: x[0]), e)
			res = max(p + memo[next], memo[i + 1])
			memo[i] = res
			maxProfit = max(maxProfit, res)
		return maxProfit

class KeyList(object):

	def __init__(self, l, key):
		self.l = l
		self.key = key

	def __len__(self):
		return len(self.l)

	def __getitem__(self, index):
		return self.key(self.l[index])


from typing import List

class Solution:

	def maximum_profit(self, N: int, A: List[List[int]]) -> int:
		A.sort()

		def Search(b, S):
			(e, ans) = (N - 1, len(A))
			while b <= e:
				m = (b + e) // 2
				if A[m][0] < S:
					b = m + 1
				else:
					e = m - 1
					ans = min(m, ans)
			return ans
		dp = [1] * N
		dp[-1] = A[-1][2]
		for i in range(N - 2, -1, -1):
			j = Search(i + 1, A[i][1])
			if j == len(A):
				dp[i] = A[i][2]
			else:
				dp[i] = A[i][2] + dp[j]
			dp[i] = max(dp[i], dp[i + 1])
		return dp[0]


from typing import List
from bisect import bisect_left

class Solution:

	def maximum_profit(self, n: int, intervals: List[List[int]]) -> int:
		intervals.sort()
		St = [i for (i, j, k) in intervals]
		dp = [0] * (n + 1)
		for k in reversed(range(n)):
			(_, e, p) = intervals[k]
			temp = bisect_left(St, e)
			dp[k] = max(p + dp[temp], dp[k + 1])
		return dp[0]


from typing import List
import bisect

class Solution:

	def maximum_profit(self, n: int, interval: List[List[int]]) -> int:
		jobs = sorted(interval, key=lambda x: x[1])
		dp = [[0, 0]]
		for (s, e, p) in jobs:
			i = bisect.bisect(dp, [s + 1]) - 1
			if dp[i][1] + p > dp[-1][1]:
				dp.append([e, dp[i][1] + p])
		return dp[-1][1]


from typing import List
from bisect import bisect_left

class Solution:

	def maximum_profit(self, n: int, intervals: List[List[int]]) -> int:
		intervals.sort()
		dp = [0] * (n + 1)
		for i in range(n - 1, -1, -1):
			(s, e, p) = intervals[i]
			j = bisect_left(intervals, [e, e, 0])
			dp[i] = max(dp[i + 1], dp[j] + p)
		return dp[0]


from typing import List
from bisect import bisect_right

class Solution:

	def maximum_profit(self, n: int, arr: List[List[int]]) -> int:
		intervals.sort(key=lambda x: x[1])
		ends = [intervals[i][1] for i in range(n)]
		profits = [0 for i in range(n)]
		profits[0] = intervals[0][2]
		for i in range(1, n):
			(s, e, p) = intervals[i]
			x = bisect_right(ends, s) - 1
			if x != -1:
				with_current = profits[x] + p
			else:
				with_current = p
			profits[i] = max(with_current, profits[i - 1])
		return profits[-1]


from typing import List
import bisect

class Solution:

	def maximum_profit(self, n: int, intervals: List[List[int]]) -> int:
		isorted = sorted(([x[1], x[0], x[2], 0, 0] for x in intervals))
		isorted[0][3] = isorted[0][2]
		imaxp_with = imaxp_without = 0
		for i in range(n):
			(iend, istart, iprofit, *_) = isorted[i]
			imaxp_without = max(imaxp_with, imaxp_without)
			imaxp_without = max(imaxp_with, imaxp_without)
			imaxp_with = iprofit
			j = bisect.bisect_left(isorted, [istart + 1], 0, i) - 1
			if j >= 0:
				imaxp_with += max(isorted[j][3:5])
			isorted[i][3] = imaxp_with
			isorted[i][4] = imaxp_without
		return max(imaxp_with, imaxp_without)


from typing import List
import sys

class Solution:

	def findlast(self, intervals, k, n):
		low = 0
		high = k
		while low <= high:
			mid = (low + high) // 2
			if intervals[mid][1] <= intervals[k][0]:
				if intervals[mid + 1][1] <= intervals[k][0]:
					low = mid + 1
				else:
					return mid
			else:
				high = mid - 1
		return -1

	def maximum_profit(self, n: int, intervals: List[List[int]]) -> int:
		if n == 0:
			return 0
		intervals.sort(key=lambda x: x[1])
		dp = [0] * n
		dp[0] = intervals[0][2]
		for i in range(1, n):
			k = self.findlast(intervals, i, n)
			inc = intervals[i][2]
			if k != -1:
				inc += dp[k]
			dp[i] = max(dp[i - 1], inc)
		return dp[n - 1]