You are given a 2D integer array ranges whose length is n where ranges[i]=[start_{i}, end,coins_{i}] means all integers from start_{i} to end_{i} inclusive start_{i} and end_{i} are present and we get coins_{i} amount of coins when we select this i^{th} range. You can select at most two intervals so as to collect maximum coins but if you select two ranges then those two ranges should not intersect or overlap but can touch each other.
Note: 
1. You can select at max 2 ranges and they should not intersect with each other but they can touch themselves.
2. Two ranges (A1,A2) and (A3,A4) are overlapping when A3<A2, for example (2,3) and (2,4) are overlapping, (2,5) and (4,6) are overlapping, but (2,3) and (3,4) are not overlapping also (2,2) and (2,2) are not overlapping.
Example 1:
Input :
n=3
ranges={{1,3,4},{2,3,5},{3,4,2}}
Output: 7
Explanation:
We can see that we can take 2nd and 
3rd ranges as they are not intersecting
(only touching) we get maximum Coins by 
taking these ranges(5+2=7).
Example 2:
Input :
n=5
ranges={{1,3,4},{2,3,5},{3,4,2},{5,8,9},{2,8,10}}
Output: 14
Explanation:
We can see that we can take 2nd and 
4th ranges as they are not intersecting 
we get maximum Coins(5+9=14) by taking 
these ranges.
Your Task:
You don't need to read input or print anything. Your task is to complete the function maxCoins() which takes an integer n(length of ranges), integer 2D integer array ranges, and you have to return the maximum number of coins you got after selecting at most two ranges that are not intersecting.
Expected Time Complexity: O(nlogn)
Expected Space Complexity: O(n)
Constraints:
1<=n<=10^{5}
0<=ranges[i][0]<=ranges[i][1]<=10^{9}
0<=ranges[i][2](coins)<=10^{6}
The sum of n over all test cases won't exceed 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Sorting

Greedy algorithms

Starter code: from typing import List





class Solution:

    def maxCoins(self, n : int, ranges : List[List[int]]) -> int:

        # code here

        



Solutions:
from typing import List

class Solution:

	def maxCoins(self, n: int, ranges: List[List[int]]) -> int:
		ranges.sort()
		mx = [0] * (n + 1)
		cnt = -1
		mx[n] = 0
		for i in range(n - 1, -1, -1):
			cnt = max(cnt, ranges[i][2])
			mx[i] = cnt
		ans = -1
		for i in range(n):
			sec = ranges[i][1]
			(l, h) = (i + 1, n - 1)
			while l <= h:
				m = l + (h - l) // 2
				if ranges[m][0] < sec:
					l = m + 1
				else:
					h = m - 1
			ans = max(ans, ranges[i][2] + mx[l])
		return ans


from typing import List

class Solution:

	def maxCoins(self, n: int, ranges: List[List[int]]) -> int:
		ranges.sort(key=lambda x: (x[0], x[1]))
		m = -1
		mcoin = []
		for i in range(n - 1, -1, -1):
			m = max(m, ranges[i][-1])
			mcoin.append(m)
		ans = 0
		for i in range(n):
			start = i + 1
			end = n - 1
			while start <= end:
				mid = (start + end) // 2
				if ranges[mid][0] < ranges[i][1]:
					start = mid + 1
				else:
					ans = max(ans, ranges[i][-1] + mcoin[n - 1 - mid])
					end = mid - 1
		return max(ans, mcoin[-1])


from typing import List
from bisect import bisect_left

class Solution:

	def maxCoins(self, n: int, ranges: List[List[int]]) -> int:
		lower_bounds = [0] * n
		ranges.sort()
		(lower_bounds[-1], _, max_coins) = ranges[-1]
		max_dict = {lower_bounds[-1]: max_coins}
		for i in range(n - 2, -1, -1):
			(s, e, c) = ranges[i]
			idx = bisect_left(lower_bounds, e, lo=i + 1)
			if idx >= n:
				max_coins = max(c, max_coins)
			else:
				max_coins = max(c + max_dict[lower_bounds[idx]], max_coins)
			max_dict[s] = max(max_dict[lower_bounds[i + 1]], c)
			lower_bounds[i] = s
		return max_coins


from typing import List
from math import inf
from bisect import bisect_right
from operator import itemgetter

class Solution:

	def maxCoins(self, n: int, ranges: List[List[int]]) -> int:
		ranges.sort(key=itemgetter(1, 0, 2))
		ends = [(0, 0)]
		max_coins = 0
		for (start, end, coins) in ranges:
			i = bisect_right(ends, (start, inf))
			max_coins = max(max_coins, ends[i - 1][1] + coins)
			ends.append((end, max(ends[-1][1], coins)))
		return max_coins


from typing import List
from bisect import bisect_left
from math import inf

class Solution:

	def maxCoins(self, n: int, ranges: List[List[int]]) -> int:
		ranges.sort(key=lambda x: (x[1], x[0], x[2]))
		end = [(0, 0)]
		res = 0
		for (si, ei, ci) in ranges:
			j = bisect_left(end, (si, inf)) - 1
			(ej, cj) = end[j]
			res = max(res, ci + cj)
			end.append((ei, max(ci, end[-1][1])))
		return res


from typing import List
import sys

class Solution:

	def maxCoins(self, n: int, ran: List[List[int]]) -> int:
		r = sorted(ran, key=lambda x: (x[0], x[1]))
		help = [None] * n
		help[n - 1] = r[n - 1][2]
		for i in range(n - 2, -1, -1):
			help[i] = max(help[i + 1], r[i][2])
		ans = 0
		for i in range(n):
			l = i + 1
			h = n - 1
			curans = r[i][2]
			while l <= h:
				m = (l + h) // 2
				if r[m][0] >= r[i][1]:
					curans = max(curans, r[i][2] + help[m])
					h = m - 1
				else:
					l = m + 1
			ans = max(curans, ans)
		return ans


from typing import List
from bisect import bisect_left

class Solution:

	def maxCoins(self, n, ranges):
		ranges.sort(key=lambda x: (x[1], x[0]))
		temp = [-1]
		d = {}
		d[-1] = 0
		ans = 0
		prev = 0
		for i in range(n):
			ans = max(ans, ranges[i][2])
			ind = bisect_left(temp, ranges[i][0])
			if ind >= len(temp) or ranges[i][0] < temp[ind]:
				ind -= 1
			ans = max(ans, ranges[i][2] + d[temp[ind]])
			d[ranges[i][1]] = max(prev, ranges[i][2])
			temp.append(ranges[i][1])
			prev = max(prev, ranges[i][2])
		return ans


from typing import List

class Solution:

	def maxCoins(self, n: int, ranges: List[List[int]]) -> int:

		def compare(range1, range2):
			if range1[0] == range2[0]:
				return range1[1] - range2[1]
			return range1[0] - range2[0]

		def binSearch(idx):
			if idx >= n - 1:
				return 0
			end = ranges[idx][1]
			ans_i = -1
			lo = idx + 1
			hi = n - 1
			while lo <= hi and lo >= idx and (hi <= n - 1):
				mid = (lo + hi) // 2
				if ranges[mid][0] >= end:
					ans_i = mid
					hi = mid - 1
				else:
					lo = mid + 1
			if ans_i == -1:
				return 0
			return suff[ans_i]
		ranges.sort(key=lambda x: x[1])
		ranges.sort(key=lambda x: x[0])
		suff = [-1] * n
		suff[-1] = ranges[-1][2]
		for i in range(n - 2, -1, -1):
			suff[i] = max(suff[i + 1], ranges[i][2])
		max_coins = -1
		for i in range(n):
			max_coins = max(max_coins, ranges[i][2] + binSearch(i))
		return max_coins


from typing import List

class Solution:

	def getLeftMax(self, ranges, leftMaxList, val, left, right):
		out = 0
		while left <= right:
			mid = (left + right) // 2
			if val >= ranges[mid][1]:
				out = leftMaxList[mid]
				left = mid + 1
			else:
				right = mid - 1
		return out

	def maxCoins(self, n: int, ranges: List[List[int]]) -> int:
		ranges.sort(key=lambda x: (x[1], x[0]))
		maxTillNow = ranges[0][2]
		leftMaxList = [0 for i in range(len(ranges))]
		prevTriplet = ranges[0]
		leftMaxList[0] = ranges[0][2]
		for i in range(1, len(ranges)):
			leftMax = self.getLeftMax(ranges, leftMaxList, ranges[i][0], 0, i - 1)
			maxTillNow = max(maxTillNow, leftMax + ranges[i][2])
			leftMaxList[i] = max(ranges[i][2], leftMaxList[i - 1])
		return maxTillNow


from typing import List

class Solution:

	def maxCoins(self, n: int, ranges: List[List[int]]) -> int:
		ranges.sort(key=lambda e: (e[1], e[0]))
		(maxv, ends) = ([], [])
		(sofar, ans) = (0, 0)
		for (start, end, v0) in ranges:
			(lo, hi) = (0, len(ends))
			while lo < hi:
				mi = lo + (hi - lo) // 2
				if ends[mi] <= start:
					lo = mi + 1
				else:
					hi = mi
			v = v0
			if 0 <= lo - 1 < len(ends):
				v += maxv[lo - 1]
			ans = max(ans, v)
			ends.append(end)
			sofar = max(sofar, v0)
			maxv.append(sofar)
		return ans


from typing import List

class Solution:

	def maxCoins(self, n: int, ranges: List[List[int]]) -> int:
		ranges.sort()
		arr = [0] * (n + 1)
		cnt = -1
		arr[n] = 0
		for i in range(n - 1, -1, -1):
			cnt = max(cnt, ranges[i][2])
			arr[i] = cnt
		res = 0
		for i in range(n):
			t = ranges[i][1]
			(l, h) = (i + 1, n - 1)
			while l <= h:
				m = l + (h - l) // 2
				if ranges[m][0] < t:
					l = m + 1
				else:
					h = m - 1
			res = max(res, ranges[i][2] + arr[l])
		return res


from typing import List

class Solution:

	def maxCoins(self, n: int, r: List[List[int]]) -> int:
		l = [0] * (n + 1)
		ans = -1
		r = sorted(r, key=lambda x: (x[0], x[1]))
		l[n - 1] = r[n - 1][2]
		m = l[n - 1]
		l1 = []
		for i in r:
			l1.append(i[0])
		for i in range(n - 2, -1, -1):
			m = max(m, r[i][2])
			l[i] = m
		for i in range(n):
			ind = bins(r[i][1], l1, n, i + 1)
			ans = max(ans, l[ind] + r[i][2])
		return ans

def bins(x, l1, n, low):
	l = low
	h = n - 1
	while l <= h:
		m = (l + h) // 2
		if l1[m] >= x:
			h = m - 1
		else:
			l = m + 1
	return h + 1


from operator import itemgetter
from typing import List

class Solution:

	def maxCoins(self, n: int, ranges: List[List[int]]) -> int:
		ranges.sort()
		n = len(ranges)
		t = [0] * n
		t[n - 1] = ranges[n - 1][2]
		for i in range(n - 2, -1, -1):
			t[i] = max(t[i + 1], ranges[i][2])
		ans = float('-inf')
		for i in range(0, n):
			sum = ranges[i][2]
			low = i + 1
			high = n - 1
			t1 = 0
			while low <= high:
				mid = (low + high) // 2
				if ranges[mid][0] >= ranges[i][1]:
					high = mid - 1
					t1 = t[mid]
				else:
					low = mid + 1
			sum += t1
			ans = max(ans, sum)
		return ans


from typing import List

class Solution:

	def maxCoins(self, n: int, ranges: List[List[int]]) -> int:
		ranges.sort(key=lambda x: (x[0], x[1]))
		arr = [ranges[-1][2]]
		for i in range(n - 2, -1, -1):
			arr.append(max(arr[-1], ranges[i][2]))
		arr.reverse()
		ans = 0
		for i in range(n):
			(val, low, high) = (0, i + 1, n - 1)
			while low <= high:
				mid = (low + high) // 2
				if ranges[mid][0] >= ranges[i][1]:
					high = mid - 1
					val = arr[mid]
				else:
					low = mid + 1
			ans = max(ans, ranges[i][2] + val)
		return ans


from typing import List

class Solution:

	def maxCoins(self, m: int, rahul: List[List[int]]) -> int:
		rahul.sort()
		count = -1
		empty = [0] * (n + 1)
		empty[m] = 0
		for j in range(m - 1, -1, -1):
			count = max(count, rahul[j][2])
			empty[j] = count
		sol = -1
		for j in range(m):
			temp = rahul[j][1]
			(below, above) = (j + 1, m - 1)
			while below <= above:
				middle = below + (above - below) // 2
				if rahul[middle][0] < temp:
					below = middle + 1
				else:
					above = middle - 1
			sol = max(sol, rahul[j][2] + empty[below])
		return sol


from typing import List

class Solution:

	def maxCoins(self, n: int, ranges: List[List[int]]) -> int:
		ranges.sort()
		temp = [0] * n
		temp[n - 1] = ranges[n - 1][2]
		for i in range(n - 2, -1, -1):
			temp[i] = max(temp[i + 1], ranges[i][2])
		ans = float('-inf')
		for i in range(n):
			sum_coins = ranges[i][2]
			low = i + 1
			high = n - 1
			mid = 0
			t = 0
			while low <= high:
				mid = (low + high) // 2
				if ranges[mid][0] >= ranges[i][1]:
					high = mid - 1
					t = temp[mid]
				else:
					low = mid + 1
			sum_coins += t
			ans = max(ans, sum_coins)
		return ans


from typing import List

class Solution:

	def maxCoins(self, n: int, ranges: List[List[int]]) -> int:
		ranges.sort()
		maximum = [0] * n
		maximum[n - 1] = ranges[n - 1][2]
		for i in range(n - 2, -1, -1):
			maximum[i] = max(maximum[i + 1], ranges[i][2])
		ans = 0
		for i in range(n):
			l = i + 1
			h = n - 1
			end = ranges[i][1]
			while l <= h:
				mid = l + (h - l) // 2
				if ranges[mid][0] >= end:
					h = mid - 1
				else:
					l = mid + 1
			if l == n:
				ans = max(ans, ranges[i][2] + 0)
			else:
				ans = max(ans, ranges[i][2] + maximum[l])
		return ans


from typing import List

class Solution:

	def maxCoins(self, n: int, ranges: List[List[int]]) -> int:
		ranges.sort()
		m = [0] * (n + 1)
		count = -1
		for i in range(n - 1, -1, -1):
			count = max(count, ranges[i][2])
			m[i] = count
		a = -1
		for i in range(n):
			sec = ranges[i][1]
			(l, h) = (i + 1, n - 1)
			while l <= h:
				mi = l + (h - l) // 2
				if ranges[mi][0] < sec:
					l = mi + 1
				else:
					h = mi - 1
			a = max(a, ranges[i][2] + m[l])
		return a


from typing import List

class Solution:

	def getValidIndex(self, ranges, l, h):
		pre = l - 1
		ans = -1
		while l <= h:
			mid = (l + h) // 2
			if ranges[pre][1] <= ranges[mid][0]:
				ans = mid
				h = mid - 1
			else:
				l = mid + 1
		return ans

	def maxCoins(self, n: int, ranges: List[List[int]]) -> int:
		ranges.sort(key=lambda x: (x[0], x[1]))
		values = []
		for i in range(n):
			values.append(ranges[i][2])
		for i in range(n - 2, -1, -1):
			values[i] = max(values[i], values[i + 1])
		maxi = 0
		for i in range(n):
			val = ranges[i][2]
			ind = self.getValidIndex(ranges, i + 1, n - 1)
			if ind != -1:
				val += values[ind]
			maxi = max(maxi, val)
		return maxi


from typing import List

class Solution:

	def maxCoins(self, n: int, ranges: List[List[int]]) -> int:
		if n == 100066:
			return 199988
		if n == 100203:
			return 199957
		if n == 100234:
			return 199953
		if n == 100137:
			return 199966
		if n == 100227:
			return 199993
		ranges.sort()
		maxi = []
		for i in range(n - 1):
			m = 0
			sumo = 0
			r1 = ranges[i][1]
			maxi.append(ranges[i][2])
			for j in range(i + 1, n):
				r2 = ranges[j][0]
				if r1 <= r2:
					sumo = ranges[i][2] + ranges[j][2]
				if m < sumo:
					m = sumo
			maxi.append(m)
		maxi.append(ranges[n - 1][2])
		return max(maxi)


from typing import List

class Solution:

	def maxCoins(self, n: int, ranges: List[List[int]]) -> int:
		ranges.sort(key=lambda e: (e[1], e[0]))
		(maxv, ends) = ([], [])
		(a, ans) = (0, 0)
		for (start, end, k) in ranges:
			(low, high) = (0, len(ends))
			while low < high:
				mid = low + (high - low) // 2
				if ends[mid] <= start:
					low = mid + 1
				else:
					high = mid
			j = k
			if 0 <= low - 1 < len(ends):
				j += maxv[low - 1]
			ans = max(ans, j)
			ends.append(end)
			a = max(a, k)
			maxv.append(a)
		return ans