We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i].
You're given the startTime , endTime and profit arrays, you need to output the maximum profit you can take such that there are no 2 jobs in the subset with overlapping time range.
If you choose a job that ends at time X you will be able to start another job that starts at time X.
 
Example 1:

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120
Explanation: The subset chosen is the first and fourth job. 
Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.

Example 2:
 

Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
Output: 150
Explanation: The subset chosen is the first, fourth and fifth job. 
Profit obtained 150 = 20 + 70 + 60.

Example 3:

Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
Output: 6

 
Constraints:

1 <= startTime.length == endTime.length == profit.length <= 5 * 10^4
1 <= startTime[i] < endTime[i] <= 10^9
1 <= profit[i] <= 10^4

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Sorting

Data structures

Starter code: class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        

Solutions:
class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		dp = [(0, 0)]
		task = [(startTime[i], endTime[i], profit[i]) for i in range(len(startTime))]
		task = sorted(task, key=lambda x: x[1])
		for (s, e, p) in task:
			noTaskProf = dp[-1][1]
			for (end, pro) in reversed(dp):
				if end <= s:
					doTaskProf = pro + p
					break
			if doTaskProf > noTaskProf:
				dp.append((e, doTaskProf))
		return dp[-1][1]


from heapq import *

class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		jobs = sorted(zip(startTime, endTime, profit))
		heap = []
		max_profit = 0
		for (start, end, p) in jobs:
			while heap and heap[0][0] <= start:
				max_profit = max(max_profit, heappop(heap)[1])
			heappush(heap, (end, max_profit + p))
		for (_, p) in heap:
			max_profit = max(max_profit, p)
		return max_profit


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		jobs = sorted(zip(startTime, endTime, profit), key=lambda v: v[1])
		dp = [(0, 0)]

		def find(time):
			size = len(dp)
			for i in range(size - 1, -1, -1):
				pre_time = dp[i][0]
				if pre_time <= time:
					return dp[i][1]
		for (s, e, p) in jobs:
			dp.append((e, max(find(e), find(s) + p)))
		return dp[-1][1]


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		dp = [0] * len(profit)
		intervals = [(startTime[i], endTime[i], profit[i]) for i in range(len(startTime))]
		intervals.sort(key=lambda x: x[1])
		dp[0] = intervals[0][2]
		for j in range(1, len(dp)):
			dp[j] = max(intervals[j][2], dp[j - 1])
			l = 0
			r = len(intervals) - 1
			while l < r:
				mid = l + (r - l + 1 >> 1)
				if intervals[mid][1] <= intervals[j][0]:
					l = mid
				else:
					r = mid - 1
			if intervals[j][0] >= intervals[l][1]:
				dp[j] = max(dp[j], intervals[j][2] + dp[l])
		return dp[-1]


class Solution:

	def binSearch(self, stack: List[int], target: int) -> List[int]:
		left = 0
		right = len(stack) - 1
		while left <= right:
			mid = (left + right + 1) // 2
			if stack[mid][1] > target:
				right = mid - 1
			elif stack[mid][1] == target or (left == right and stack[mid][1] < target):
				return stack[mid]
			else:
				left = mid
		return None

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		n = len(startTime)
		jobs = [[startTime[i], endTime[i], profit[i]] for i in range(n)]
		jobs.sort(key=lambda x: x[1])
		stack = []
		for i in range(n):
			job = jobs[i]
			prev = self.binSearch(stack, job[0])
			if prev is not None:
				job[2] += prev[2]
			if not stack or stack[-1][2] < job[2]:
				stack.append(job)
		return stack[-1][2]


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		res = sorted(zip(startTime, endTime, profit), key=lambda x: x[0])
		unzipped_res = list(zip(*res))
		startTime = unzipped_res[0]
		endTime = unzipped_res[1]
		profit = unzipped_res[2]
		return self.backwardDP(startTime, endTime, profit)

	def topDown(self, startTime, endTime, profit):
		N = len(startTime)

		@lru_cache(None)
		def solve(i):
			if i == N:
				return 0
			start = startTime[i]
			end = endTime[i]
			nextI = N
			for j in range(i + 1, N):
				if startTime[j] >= end:
					nextI = j
					break
			prof = profit[i]
			taken = solve(nextI) + profit[i]
			notTaken = solve(i + 1)
			return max(taken, notTaken)
		amt = solve(0)
		return amt

	def backwardDP(self, startTime, endTime, profit):
		from bisect import bisect_left
		N = len(startTime)
		OPT = [0 for i in range(N + 1)]
		for i in range(N - 1, -1, -1):
			start = startTime[i]
			end = endTime[i]
			prof = profit[i]
			freeK = N
			freeK = bisect_left(startTime, end)
			take = profit[i] + OPT[freeK]
			dontTake = OPT[i + 1]
			OPT[i] = max(take, dontTake)
		return OPT[0]

	def forwardDP(self, startTime, endTime, profit):
		N = len(startTime)
		OPT = [profit[i] for i in range(N)]
		for i in range(N):
			prof = profit[i]
			end = endTime[i]
			x = bisect_left(startTime, end)
			for k in range(x, N):
				OPT[k] += prof
		return OPT[-1]


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		intervals = sorted(zip(startTime, endTime, profit), key=lambda x: (x[1], x[2]))
		N = len(profit)
		dp = [(0, 0, 0)]
		for (idx, (s, e, p)) in enumerate(intervals):
			nonoverlapping_idx = self.find_nonoverlapping_interval(dp, s + 0.1)
			if dp[nonoverlapping_idx][0] + p > dp[idx - 1 + 1][0]:
				dp.append((dp[nonoverlapping_idx][0] + p, e, idx))
			else:
				dp.append(dp[idx - 1 + 1])
		solutions = []
		cur_idx = N
		while cur_idx != 0:
			solutions.append(cur_idx)
			solution = self.find_nonoverlapping_interval(dp, intervals[dp[cur_idx][2]][0])
			cur_idx = dp[solution][2]
			solutions.append(cur_idx)
		print(solutions)
		return dp[-1][0]

	def find_nonoverlapping_interval(self, dp, start):
		l_idx = 0
		r_idx = len(dp) - 1
		while r_idx >= 0 and l_idx < len(dp) and (l_idx <= r_idx):
			mid_idx = (l_idx + r_idx) // 2
			if dp[mid_idx][1] < start:
				l_idx = mid_idx + 1
			else:
				r_idx = mid_idx - 1
		return l_idx - 1


from collections import defaultdict

class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		times = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])
		n = len(endTime)
		dp = [(0, 0)]

		def bsearch(arr, target):
			(start, end) = (0, len(arr) - 1)
			while start < end:
				mid = (end - start) // 2 + start
				if arr[mid][0] == target:
					return mid
				elif arr[mid][0] > target:
					end = mid - 1
				else:
					start = mid + 1
			return start if target >= arr[start][0] else start - 1
		for i in range(1, n + 1):
			(start, end, p) = times[i - 1]
			last_start = bsearch(dp, start)
			if len(dp) > last_start >= 0:
				dp.append((end, max(dp[last_start][1] + p, dp[-1][1])))
			else:
				dp.append((end, p))
		return dp[n][1]


class Solution:

	def binsearch(self, arr, ele, l, r):
		while r - l > 1:
			mid = l + (r - l) // 2
			if arr[mid][1] == ele:
				return mid
			elif arr[mid][1] > ele:
				r = mid
			else:
				l = mid
		return l

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		n = len(startTime)
		dp = [0] * n
		times = []
		for i in range(n):
			times.append([startTime[i], endTime[i], profit[i]])
		times.sort(key=lambda it: it[1])
		dp[0] = times[0][2]
		for i in range(1, n):
			prof = times[i][2]
			binInd = self.binsearch(times, times[i][0], -1, i)
			if binInd != -1:
				prof += dp[binInd]
			dp[i] = max(dp[i - 1], prof)
		return dp[n - 1]


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		jobs = sorted(zip(startTime, endTime, profit), key=lambda v: v[1])
		dp = [0 for j in range(len(jobs))]
		for i in range(len(jobs)):
			if i == 0:
				inc_n = 0
			else:
				inc_n = dp[i - 1]
			ind = self.find(jobs, jobs[i][0])
			if ind == -1:
				inc = jobs[i][2]
			else:
				inc = dp[ind] + jobs[i][2]
			dp[i] = max(inc, inc_n)
		print(dp)
		return dp[-1]

	def find(self, arr, val):
		l = 0
		r = len(arr) - 1
		ans = -1
		while l <= r:
			m = (l + r) // 2
			if arr[m][1] > val:
				r = m - 1
			else:
				ans = m
				l = m + 1
		return ans


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])

		def binary_search(val: int):
			nonlocal jobs
			if val < jobs[0][1]:
				return -1
			if val >= jobs[-1][1]:
				return len(jobs) - 1
			(start, end) = (0, len(jobs) - 1)
			while start < end - 1:
				mid = start + (end - start) // 2
				if jobs[mid][1] < val:
					start = mid
				elif jobs[mid][1] > val:
					end = mid - 1
				else:
					return mid
			return end if jobs[end][1] <= val else start
		most_recent = [0] * len(jobs)
		for (i, job) in enumerate(jobs):
			most_recent[i] = binary_search(job[0])
		dp_profits = [0] * len(jobs)
		for (i, job) in enumerate(jobs):
			most_recents_profit = 0 if most_recent[i] == -1 else dp_profits[most_recent[i]]
			prev_profit = 0 if i == 0 else dp_profits[i - 1]
			dp_profits[i] = max(job[2] + most_recents_profit, prev_profit)
		return dp_profits[-1]


import collections
import functools
import heapq
import itertools
import sys
from functools import lru_cache
from typing import List

class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:

		def dfs_func():
			n = len(profit)
			dp = {}
			jobs = [(startTime[i], endTime[i], profit[i]) for i in range(n)]
			jobs.sort()

			def find_next_confict(jobs_i):
				for jobs_j in range(jobs_i + 1, n):
					if jobs[jobs_i][1] <= jobs[jobs_j][0]:
						return jobs_j
				return n

			def find_next_confict_left(jobs_i):
				dst = jobs[jobs_i][1]
				left = jobs_i
				right = n
				while left < right:
					mid = int((left + right) / 2)
					mid_value = jobs[mid][0]
					if dst < mid_value:
						right = mid
					elif dst > mid_value:
						left = mid + 1
					else:
						right = mid
				return left

			def dfs(jobs_i):
				if jobs_i >= n:
					return 0
				if jobs_i in dp:
					return dp[jobs_i]
				(s, e, p) = jobs[jobs_i]
				jobs_j = find_next_confict_left(jobs_i)
				choose = p
				if jobs_j < n:
					choose += dfs(jobs_j)
				not_choose = dfs(jobs_i + 1)
				dp[jobs_i] = max(choose, not_choose)
				return dp[jobs_i]
			return dfs(0)

		def dp_func():
			n = len(profit)
			jobs = [(endTime[i], startTime[i], profit[i]) for i in range(n)]
			jobs.sort()
			dp = [0 for _ in range(n + 1)]

			def find_pre_not_confict(jobs_i):
				dst = jobs[jobs_i][1]
				left = 0
				right = jobs_i
				while left < right:
					mid = int((left + right) / 2)
					mid_value = jobs[mid][0]
					if dst < mid_value:
						right = mid
					elif dst > mid_value:
						left = mid + 1
					else:
						left = mid + 1
				return left - 1

			def find_pre_not_confict1(jobs_i):
				for i in range(jobs_i, -1, -1):
					if jobs[jobs_i][1] >= jobs[i][0]:
						return i
				return -1
			for i in range(1, n + 1):
				last_not_conflict = find_pre_not_confict(i - 1)
				choose = jobs[i - 1][2]
				if last_not_conflict != -1:
					choose += dp[last_not_conflict + 1]
				dp[i] = max(dp[i - 1], choose)
			return dp[n]
		return dp_func()


class Solution:

	def jobScheduling(self, S: List[int], E: List[int], profit: List[int]) -> int:
		n = len(S)
		jobs = sorted([(S[i], E[i], profit[i]) for i in range(n)], key=lambda x: x[1])
		S = [jobs[i][0] for i in range(n)]
		E = [jobs[i][1] for i in range(n)]
		profit = [jobs[i][2] for i in range(n)]
		dp = [-1] * n
		dp[0] = (profit[0], E[0])
		for i in range(1, n):
			(prev_profit, endTime) = dp[i - 1]
			startTime = S[i]
			left = 0
			right = i - 1
			ans = profit[i]
			while left <= right:
				mid = (left + right) // 2
				if dp[mid][1] <= startTime:
					ans = max(ans, profit[i] + dp[mid][0])
					left = mid + 1
				else:
					right = mid - 1
			if ans > prev_profit:
				dp[i] = (ans, E[i])
			else:
				dp[i] = dp[i - 1]
		return max([ele[0] for ele in dp])


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		n = len(startTime)
		jobs = list(zip(endTime, startTime, profit))
		jobs.sort()

		def binary_search(jobs, i):
			left = 0
			right = i - 1
			while left <= right:
				mid = (left + right) // 2
				if jobs[mid][0] <= jobs[i][1]:
					if jobs[mid + 1][0] <= jobs[i][1]:
						left = mid + 1
					else:
						return mid
				else:
					right = mid - 1
			return -1
		dp = [0] * n
		dp[0] = jobs[0][2]
		for i in range(1, n):
			k = binary_search(jobs, i)
			if k != -1:
				dp[i] = max(dp[k] + jobs[i][2], dp[i - 1])
			else:
				dp[i] = max(jobs[i][2], dp[i - 1])
		return dp[n - 1]


from sortedcontainers import SortedList

class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		lst = sorted(zip(startTime, endTime, profit))
		(maxprofit, tempstck) = (0, SortedList())
		for i in range(len(lst)):
			(curr_strt, curr_end, curr_price) = lst[i]
			while tempstck and -tempstck[-1][0] <= curr_strt:
				maxprofit = max(tempstck.pop()[1], maxprofit)
			curr_maxprofit = maxprofit + curr_price
			tempstck.add((-curr_end, curr_maxprofit))
		return max(maxprofit, *(i[1] for i in tempstck))


from bisect import bisect_right

class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		(pair, N) = (sorted(enumerate(endTime), key=lambda tup: tup[1]), len(endTime))
		(endTime, startTime, profit) = ([e for (_, e) in pair], [startTime[i] for (i, _) in pair], [profit[i] for (i, _) in pair])
		dp = [0] * (N + 1)
		for (i, s) in enumerate(startTime):
			j = bisect_right(endTime, s, 0, i) - 1
			dp[i] = max(dp[i - 1], dp[j] + profit[i])
		return dp[N - 1]


class Solution:

	def findPreviousJob(self, jobs, curIdx):
		low = 0
		high = curIdx - 1
		while low < high:
			mid = low + (high - low + 1) // 2
			if jobs[mid].end <= jobs[curIdx].start:
				low = mid
			else:
				high = mid - 1
		return low

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		jobs = []
		for i in range(len(profit)):
			job = Job(startTime[i], endTime[i], profit[i])
			jobs.append(job)
		jobs.sort(key=lambda x: x.end)
		dp = [0] * len(jobs)
		dp[0] = jobs[0].profit
		for i in range(1, len(jobs)):
			dp[i] = jobs[i].profit
			index = self.findPreviousJob(jobs, i)
			if jobs[index].end <= jobs[i].start:
				dp[i] += dp[index]
			dp[i] = max(dp[i - 1], dp[i])
		return dp[len(jobs) - 1]

class Job:

	def __init__(self, start, end, profit):
		self.start = start
		self.end = end
		self.profit = profit


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		l = [(startTime[i], endTime[i], profit[i]) for i in range(len(startTime))]
		l = sorted(l, key=lambda x: x[1])
		ma = 0

		def binarysearch(x):
			left = 0
			right = x
			while left < right:
				mid = (left + right) // 2
				if l[mid][1] <= l[x][0]:
					if l[mid + 1][1] <= l[x][0]:
						left = mid + 1
					else:
						return mid
				else:
					right = mid - 1
			return left
		dp = [0] * len(startTime)
		for i in range(len(startTime)):
			dp[i] = max(dp[i - 1], l[i][2])
			p = binarysearch(i)
			if l[p][1] <= l[i][0]:
				dp[i] = max(dp[i], dp[p] + l[i][2])
		return dp[-1]


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:

		def bisect(arr, num, l, r):
			if l >= r:
				return l
			mid = (l + r + 1) // 2
			if arr[mid][2] > num:
				return bisect(arr, num, l, mid - 1)
			else:
				return bisect(arr, num, mid, r)
		n = len(startTime)
		timeslots = [(profit[i], startTime[i], endTime[i]) for i in range(n)]
		timeslots = sorted(timeslots, key=lambda a: a[2])
		dp = [0] * (n + 1)
		for (i, (p, s, e)) in enumerate(timeslots):
			j = bisect(timeslots, s, -1, n - 1) + 1
			dp[i + 1] = max(dp[j] + p, dp[i])
		return dp[-1]


import bisect

class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		dp = [[0, 0]]
		curinfo = sorted(list(zip(startTime, endTime, profit)), key=lambda x: x[1])
		for (s, e, p) in curinfo:
			i = bisect.bisect_right(dp, [s + 1]) - 1
			if dp[i][1] + p > dp[-1][1]:
				dp.append([e, dp[i][1] + p])
		return dp[-1][1]


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		events = []
		for (i, (start, end)) in enumerate(zip(startTime, endTime)):
			events.append((start, i + 1))
			events.append((end, -(i + 1)))
		best = 0
		for (_, idx) in sorted(events):
			if idx > 0:
				profit[idx - 1] += best
			else:
				best = max(best, profit[-idx - 1])
		return best


from functools import lru_cache

class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		jobs = [(startTime[i], endTime[i], profit[i]) for i in range(len(startTime))]
		jobs = sorted(jobs)

		@lru_cache(maxsize=None)
		def dp(i):
			if i >= len(jobs):
				return 0
			if i == len(jobs) - 1:
				return jobs[-1][2]
			(l, r) = (i + 1, len(jobs) - 1)
			j = l
			while l <= r:
				m = (l + r) // 2
				if jobs[m][0] < jobs[i][1]:
					l = m + 1
					j = max(j, m + 1)
				elif jobs[m][0] == jobs[i][1]:
					r = m - 1
					j = m
				else:
					r = m - 1
					j = m
			return max(jobs[i][2] + dp(j), dp(i + 1))
		return dp(0)


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:

		def bs(list1, target):
			left = 0
			right = len(list1) - 1
			while left < right - 1:
				mid = (left + right) // 2
				if target == list1[mid][0]:
					return list1[mid]
				elif target > list1[mid][0]:
					left = mid
				else:
					right = mid - 1
			if list1[right][0] > target:
				return list1[left]
			else:
				return list1[right]
		jobs = []
		for i in range(len(startTime)):
			jobs.append([startTime[i], endTime[i], profit[i]])
		jobs.sort(key=lambda x: x[1])
		dp = [[0, 0]]
		for job in jobs:
			maxLast = bs(dp, job[0])[1]
			if maxLast + job[2] > dp[-1][1]:
				dp.append([job[1], maxLast + job[2]])
		return dp[-1][1]


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		n = len(startTime)
		jobs = []
		for i in range(n):
			jobs.append((startTime[i], endTime[i], profit[i]))
		jobs.sort(key=lambda x: (x[1], x[0], x[2]))
		from sortedcontainers import SortedDict
		sd = SortedDict()
		result = 0
		for i in range(n):
			(start, end, profit) = jobs[i]
			previ = sd.bisect_right(start)
			if previ == 0:
				sd[end] = max(result, profit)
			else:
				prev_key = list(sd.keys())[previ - 1]
				sd[end] = max(result, profit + sd.get(prev_key))
			result = max(result, sd.get(end))
		return result


from typing import List
from functools import lru_cache

class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		intervals = sorted(zip(startTime, endTime, profit))
		n = len(intervals)

		def get_next_idx(start_idx, end_time):
			(lo, hi, res) = (start_idx, n - 1, n)
			while lo <= hi:
				mid = (hi + lo) // 2
				start_time = intervals[mid][0]
				if start_time >= end_time:
					(res, hi) = (mid, mid - 1)
				else:
					lo = mid + 1
			return res

		@lru_cache(None)
		def helper(idx):
			if idx >= n:
				return 0
			(start, end, profit) = intervals[idx]
			not_take_option = helper(idx + 1)
			take_option = profit + helper(get_next_idx(idx + 1, end))
			return max(not_take_option, take_option)
		return helper(0)


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		jobs = []
		for i in range(len(startTime)):
			jobs.append([endTime[i], startTime[i], profit[i]])
		jobs.sort()
		dp = [0] * (max(endTime) + 1)
		arr = [0]
		for job in jobs:
			prev_largest_idx = self.get_prev_idx(job[1], arr)
			curr_max = max(job[2] + dp[prev_largest_idx], dp[arr[-1]])
			dp[job[0]] = max(curr_max, dp[job[0]])
			arr.append(job[0])
		return dp[-1]

	def get_prev_idx(self, target, arr):
		if arr[-1] <= target:
			return arr[-1]
		(l, r) = (0, len(arr) - 1)
		while l < r:
			mid = l + (r - l) // 2
			if arr[mid] > target:
				r = mid
			else:
				l = mid + 1
		return arr[l - 1]


class JOB:

	def __init__(self, start, end, profit):
		self.start = start
		self.end = end
		self.profit = profit

class Solution:

	def binsearch(self, job, start_index):
		lo = 0
		hi = start_index - 1
		while lo <= hi:
			mid = lo + (hi - lo) // 2
			if job[mid].end <= job[start_index].start:
				if job[mid + 1].end <= job[start_index].start:
					lo = mid + 1
				else:
					return mid
			else:
				hi = mid - 1
		return -1

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		job = []
		n = len(profit)
		for i in range(n):
			job.append(JOB(startTime[i], endTime[i], profit[i]))
		job = sorted(job, key=lambda x: x.end)
		table = [0 for i in range(n)]
		table[0] = job[0].profit
		for i in range(1, len(profit)):
			cur_profit = job[i].profit
			l = self.binsearch(job, i)
			if l != -1:
				cur_profit += table[l]
			table[i] = max(table[i - 1], cur_profit)
		return table[-1]


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:

		def last_not_conflict(jobs, m):
			for j in range(m - 1, -1, -1):
				if jobs[j][1] <= jobs[m][0]:
					return j
			return -1

		def recursive(jobs, l):
			if l == 1:
				return jobs[0][2]
			if l in dp:
				return dp[l]
			include = jobs[l - 1][2]
			i = last_not_conflict(jobs, l - 1)
			if i != -1:
				include += recursive(jobs, i + 1)
			exclude = recursive(jobs, l - 1)
			dp[l] = max(include, exclude)
			return dp[l]
		n = len(startTime)
		jobs = [[startTime[i], endTime[i], profit[i]] for i in range(n)]
		jobs.sort(key=lambda x: x[1])
		dp = dict()
		return recursive(jobs, n)


class BIT:

	def __init__(self, n):
		self.n = n
		self.bit = [0] * (n + 1)

	def add(self, i, x):
		i += 1
		while i <= self.n:
			self.bit[i] = max(self.bit[i], x)
			i += i & -i

	def acc(self, i):
		s = 0
		while i > 0:
			s = max(s, self.bit[i])
			i -= i & -i
		return s

class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		l = startTime + endTime
		l = list(set(l))
		l.sort()
		idx = defaultdict(int)
		for i in range(len(l)):
			idx[l[i]] = i
		sep = [(idx[s], idx[e], p) for (s, e, p) in zip(startTime, endTime, profit)]
		sep.sort()
		bit = BIT(10 ** 5 + 10)
		for (s, e, p) in sep:
			bit.add(e, bit.acc(s + 1) + p)
		return bit.acc(10 ** 5 + 10)


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		n = len(startTime)
		table = sorted(zip(startTime, endTime, profit), key=lambda v: v[1])

		def find(table, x):
			l = 0
			h = n - 1
			ans = -1
			while l <= h:
				m = (l + h) // 2
				if table[m][1] == x:
					return m
				if table[m][1] < x:
					ans = m
					l = m + 1
				else:
					h = m - 1
			return ans
		dp = [0] * n
		dp[0] = table[0][2]
		mx = 0
		for i in range(1, n):
			x = table[i][0]
			loca = find(table, x)
			if loca >= 0:
				ans = table[i][2] + dp[loca]
			else:
				ans = table[i][2]
			dp[i] = max(ans, dp[i - 1])
		print(dp)
		return max(dp)


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		dp = [0 for _ in range(len(startTime))]
		intervals = [(startTime[i], endTime[i], profit[i]) for i in range(len(startTime))]
		intervals.sort()

		def findNext(curr):
			for n in range(curr + 1, len(intervals)):
				if intervals[n][0] >= intervals[curr][1]:
					return n
			return -1
		for i in range(len(intervals) - 1, -1, -1):
			(currS, currE, currP) = intervals[i]
			nextI = findNext(i)
			dp[i] = max(currP + (0 if nextI == -1 else dp[nextI]), 0 if i == len(intervals) - 1 else dp[i + 1])
		return max(dp)


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		time_table = list(zip(endTime, startTime, profit))
		time_table.sort()
		cumul_profit = [0 for i in range(len(profit))]
		cumul_profit[0] = time_table[0][2]
		for qu in range(len(time_table)):
			find = 0
			for f in range(qu - 1, -1, -1):
				if time_table[f][0] <= time_table[qu][1]:
					find = cumul_profit[f]
					break
			cumul_profit[qu] = max(cumul_profit[qu - 1], find + time_table[qu][2])
		return cumul_profit[len(profit) - 1]


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		temp = list(zip(startTime, endTime, profit))
		temp = sorted(temp, key=lambda x: x[0])
		n = len(profit)
		ans = [0 for _ in range(len(profit))]
		ans[-1] = temp[-1][2]

		def binary_s(low, high, end):
			mid = int((low + high) / 2)
			if mid == high:
				return high
			if temp[mid][0] < end and temp[mid + 1][0] >= end:
				return mid
			elif temp[mid][0] >= end:
				return binary_s(low, mid - 1, end)
			else:
				return binary_s(mid + 1, high, end)
		for x in range(n - 2, -1, -1):
			mid = binary_s(x, n - 1, temp[x][1])
			if mid != n - 1 and temp[mid + 1][0] >= temp[x][1]:
				ans[x] = max(temp[x][2] + ans[mid + 1], ans[x + 1])
			else:
				ans[x] = max(temp[x][2], ans[x + 1])
		return ans[0]


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		n = len(startTime)
		jobs = sorted(zip(startTime, endTime, profit), key=lambda v: v[1])
		dp = [0] * (n + 1)
		for (i, job) in enumerate(jobs):
			(s1, e1, p1) = (job[0], job[1], job[2])
			dp[i + 1] = p1
			for j in range(i, -1, -1):
				if jobs[j][1] <= s1:
					dp[i + 1] = max(dp[i], dp[j + 1] + job[2])
					break
			dp[i + 1] = max(dp[i], dp[i + 1])
		return dp[-1]


from sortedcontainers import SortedList

class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		jobs = []
		for i in range(len(startTime)):
			s = startTime[i]
			e = endTime[i]
			p = profit[i]
			jobs.append((e, s, p))
		jobs = sorted(jobs)
		jobs = SortedList(jobs)
		N = len(jobs)
		dp = [0 for _ in range(N)]
		dp[0] = jobs[0][2]
		for i in range(1, N):
			job = jobs[i]
			end_to_look = job[1]
			to_look_index = jobs.bisect_right((end_to_look, sys.maxsize, sys.maxsize))
			print(to_look_index)
			dp[i] = dp[i - 1]
			if to_look_index - 1 >= 0 and jobs[to_look_index - 1][0] <= job[1]:
				dp[i] = max(dp[i], dp[to_look_index - 1] + job[2])
			else:
				dp[i] = max(job[2], dp[i])
		print(dp)
		return dp[N - 1]


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		jobs = sorted(zip(startTime, endTime, profit))
		memo = {}

		def maximize_profit(start_time, min_job_id):
			if start_time in memo:
				return memo[start_time]
			i = min_job_id
			while i < len(jobs) and jobs[i][0] < start_time:
				i += 1
			max_profit = 0
			min_end_time = float('inf')
			while i < len(jobs) and jobs[i][0] < min_end_time:
				profit = jobs[i][2] + maximize_profit(jobs[i][1], i + 1)
				max_profit = max(max_profit, profit)
				min_end_time = min(min_end_time, jobs[i][1])
				i += 1
			memo[start_time] = max_profit
			return max_profit
		return maximize_profit(0, 0)


class Job:

	def __init__(self, start, end, profit):
		self.start = start
		self.end = end
		self.profit = profit

	def __lt__(self, other):
		return (self.end, self.start, self.profit) < (other.end, other.start, other.profit)

class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		n = len(startTime)
		if n == 0:
			return 0
		arr = [Job(startTime[i], endTime[i], profit[i]) for i in range(n)]
		arr.sort()
		dp = [0 for x in range(n)]
		dp[0] = arr[0].profit
		for i in range(1, n):
			job = arr[i]
			cmax = job.profit
			le = self.binarySearch(arr, i, job.start)
			if 0 <= le < i:
				cmax += dp[le]
			dp[i] = max(dp[i - 1], cmax)
		return dp[-1]

	def binarySearch(self, arr, i, start):
		(s, e) = (0, i - 1)
		while s <= e:
			m = (s + e) // 2
			if arr[m].end > start:
				e = m - 1
			elif m == e or (0 <= m + 1 < i and arr[m + 1].end > start):
				return m
			else:
				s = m + 1
		return -(s + 1)


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		n = len(startTime)
		jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[0])
		dp = [0] * n
		dp[n - 1] = jobs[n - 1][2]
		for i in range(n - 2, -1, -1):
			dp[i] = max(jobs[i][2], dp[i + 1])
			for j in range(i + 1, n):
				if jobs[i][1] <= jobs[j][0]:
					dp[i] = max(dp[i], jobs[i][2] + dp[j])
					break
		print(jobs)
		print(dp)
		return dp[0]


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		n = len(startTime)
		jobs = [(startTime[i], endTime[i], profit[i]) for i in range(n)]
		jobs.sort(key=lambda x: x[1])
		dp = [(0, 0)]

		def find(time):
			n = len(dp)
			for i in range(n - 1, -1, -1):
				if dp[i][0] <= time:
					return dp[i][1]
		for j in jobs:
			dp.append((j[1], max(j[2] + find(j[0]), find(j[1]))))
		return dp[-1][1]


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		N = len(startTime)
		endtime_ith = sorted([(endTime[i], i) for i in range(N)])
		return self.get_max_profit(max(endTime), {}, endtime_ith, startTime, endTime, profit)

	def get_max_profit(self, end, cache, endtime_ith, startTime, endTime, profit):
		if end in cache:
			return cache[end]
		k = self.floor(endtime_ith, end)
		res = 0
		if k >= 0:
			floor_ith = endtime_ith[k][1]
			boundary = startTime[floor_ith]
			while k >= 0:
				(cur_end_time, original_ith) = endtime_ith[k]
				if cur_end_time < boundary:
					break
				cur_start_time = startTime[original_ith]
				res = max(res, self.get_max_profit(cur_start_time, cache, endtime_ith, startTime, endTime, profit) + profit[original_ith])
				k -= 1
		cache[end] = res
		return res

	def floor(self, endtime_ith, end):
		res = -1
		(hi, lo) = (len(endtime_ith) - 1, 0)
		while hi >= lo:
			mid = lo + (hi - lo) // 2
			if endtime_ith[mid][0] <= end:
				res = max(res, mid)
				lo = mid + 1
			else:
				hi = mid - 1
		return res


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:

		def last_non_conflict(jobs, i):
			for j in range(i - 1, -1, -1):
				if jobs[j][1] <= jobs[i][0]:
					return j
			return -1

		def recursive(jobs, l):
			if l == 1:
				return jobs[0][2]
			if l in dp:
				return dp[l]
			include_profit = jobs[l - 1][2]
			i = last_non_conflict(jobs, l - 1)
			if i != -1:
				include_profit += recursive(jobs, i + 1)
			exclude_profit = recursive(jobs, l - 1)
			dp[l] = max(include_profit, exclude_profit)
			return dp[l]
		n = len(startTime)
		jobs = [[startTime[i], endTime[i], profit[i]] for i in range(n)]
		jobs.sort(key=lambda x: x[1])
		dp = dict()
		return recursive(jobs, n)


class Solution:

	def jobScheduling(self, startTime, endTime, profit):
		jobs = sorted(zip(startTime, endTime, profit), key=lambda v: v[1])
		dp = [0] * len(jobs)
		dp[0] = jobs[0][-1]
		for i in range(1, len(dp)):
			curProfit = jobs[i][-1]
			j = self.searchInsert(jobs, jobs[i][0])
			if j != -1:
				curProfit += dp[j]
			dp[i] = max(dp[i - 1], curProfit)
		return dp[-1]

	def searchInsert(self, nums, target: int) -> int:
		if not nums:
			return 0
		l = 0
		r = len(nums) - 1
		while l <= r:
			m = (l + r) // 2
			if nums[m][1] == target:
				return m
			elif nums[m][1] < target:
				l = m + 1
			else:
				r = m - 1
		return l - 1


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		(time_line, sz, time_mapping, f) = ([], len(profit), {}, [0] * (2 * len(profit)))
		for i in range(sz):
			(time_line.append((startTime[i], sz)), time_line.append((endTime[i], i)))
		for (index, entry) in enumerate(sorted(time_line)):
			if entry[1] < sz:
				f[index] = max(f[index - 1], f[time_mapping[startTime[entry[1]]]] + profit[entry[1]])
			else:
				f[index] = f[index - 1]
				time_mapping[entry[0]] = index
		return f[-1]


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		hel = [[startTime[i], 1, endTime[i], profit[i]] for i in range(len(startTime))]
		heapq.heapify(hel)
		res = 0
		while hel:
			ele = heapq.heappop(hel)
			if ele[1] == 1:
				heapq.heappush(hel, [ele[2], 0, ele[2], ele[-1] + res])
			else:
				res = max(res, ele[-1])
		return res


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:

		def find(i):
			l = -1
			r = i - 1
			while l < r:
				m = (l + r + 1) // 2
				if jobs[m][1] <= jobs[i][0]:
					l = m
				else:
					r = m - 1
			return l
		n = len(startTime)
		jobs = []
		for i in range(n):
			jobs.append([startTime[i], endTime[i], profit[i]])
		jobs.sort(key=lambda x: x[1])
		tot = [0 for _ in range(n + 1)]
		tot[0] = jobs[0][2]
		print(jobs)
		for i in range(1, n):
			p = find(i)
			tot[i] = max(tot[i - 1], tot[p] + jobs[i][2])
		return tot[n - 1]


import collections

class Solution:

	@staticmethod
	def binary_search(arr, i):
		lo = 0
		hi = len(arr)
		while lo < hi:
			mid = (lo + hi) // 2
			if arr[mid][0] <= i:
				lo = mid + 1
			else:
				hi = mid
		return lo

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		mapping = collections.defaultdict(list)
		for i in range(len(startTime)):
			mapping[endTime[i]].append([startTime[i], profit[i]])
		tasks = sorted(list(mapping.items()), key=lambda x: x[0])
		dp = [[0, 0]]
		for group in tasks:
			for task in group[1]:
				idx = self.binary_search(dp, task[0]) - 1
				if idx >= 0 and task[1] + dp[idx][1] > dp[-1][1]:
					if dp[-1][0] == group[0]:
						dp[-1][1] = task[1] + dp[idx][1]
					else:
						dp.append([group[0], task[1] + dp[idx][1]])
		return dp[-1][1]


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		n = len(endTime)
		endidx = defaultdict(list)
		maxt = 0
		for (i, t) in enumerate(endTime):
			endidx[t].append(i)
			maxt = max(maxt, t)
		dp = [0] * (maxt + 1)
		for t in range(1, maxt + 1):
			if t not in endidx:
				dp[t] = dp[t - 1]
			else:
				cur = dp[t - 1]
				for i in endidx[t]:
					cur = max(cur, dp[startTime[i]] + profit[i])
				dp[t] = cur
		return dp[-1]


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		intervals = []
		n = len(startTime)
		for i in range(n):
			intervals.append((startTime[i], endTime[i], profit[i]))
		intervals.sort(key=lambda x: x[1])
		T = intervals[-1][1]
		dp = [0] * (T + 1)
		co = [0] * (T + 1)
		for i in range(n):
			(s, e, p) = intervals[i]
			if dp[s] + p > dp[e]:
				dp[e] = dp[s] + p
				co[e] = co[s] + 1
			if i == n - 1:
				break
			nxte = intervals[i + 1][1] + 1
			for t in range(e + 1, nxte):
				dp[t] = dp[e]
				co[t] = co[e]
		print(co[T])
		return dp[T]


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		start = collections.defaultdict(list)
		for (i, time) in enumerate(startTime):
			start[time].append(i)
		dp = [0] * (max(endTime) + 1)
		for t in range(max(endTime) - 1, 0, -1):
			if t in start:
				for i in start[t]:
					dp[t] = max(profit[i] + dp[endTime[i]], dp[t + 1], dp[t])
			else:
				dp[t] = dp[t + 1]
		return dp[1]


from collections import defaultdict

class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		time_dict = defaultdict(list)
		for (start, end, p) in zip(startTime, endTime, profit):
			time_dict[end].append((start, p))
		n = max(endTime)
		dp = [0] * (n + 1)
		for i in range(1, n + 1):
			if i not in time_dict:
				dp[i] = dp[i - 1]
				continue
			for (start, profit) in time_dict[i]:
				curr_p = dp[start] + profit
				dp[i] = max(curr_p, dp[i], dp[i - 1])
		return dp[n]


from collections import defaultdict

class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		finish = defaultdict(list)
		for (i, j, k) in zip(startTime, endTime, profit):
			finish[j].append((i, k))
		nn = max(endTime)
		dp = [0] * (nn + 1)
		for i in range(2, nn + 1):
			if i in finish:
				for j in finish[i]:
					dp[i] = max(dp[i - 1], dp[j[0]] + j[1], dp[i])
			else:
				dp[i] = dp[i - 1]
		return dp[nn]


from collections import defaultdict

class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		n = max(endTime)
		lookup = defaultdict(list)
		for (s, e, p) in zip(startTime, endTime, profit):
			lookup[e].append((s, p))
		dp = [0] * (n + 1)
		for i in range(1, len(dp)):
			dp[i] = dp[i - 1]
			if i in lookup:
				for (start, prof) in lookup[i]:
					dp[i] = max(dp[i], dp[start] + prof)
		return dp[-1]


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		l = len(startTime)
		sep = list(zip(endTime, startTime, profit))
		sep = sorted(sep)
		dp = [0] * (sep[-1][0] + 1)
		j = 0
		for i in range(2, len(dp)):
			if sep[j][0] != i:
				dp[i] = dp[i - 1]
			else:
				dp[i] = max(dp[i - 1], sep[j][2] + dp[sep[j][1]])
				j += 1
				while j < l and sep[j][0] == sep[j - 1][0]:
					dp[i] = max(dp[i], sep[j][2] + dp[sep[j][1]])
					j += 1
		return dp[-1]


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		last_dict = {}
		for i in range(len(startTime)):
			if endTime[i] not in last_dict:
				last_dict[endTime[i]] = []
			last_dict[endTime[i]].append((startTime[i], profit[i]))
		last_end = max(endTime)
		result = [0] * (last_end + 1)
		for t in range(1, len(result)):
			max_val = result[t - 1]
			if t in last_dict:
				for (start, profit) in last_dict[t]:
					max_val = max(result[start] + profit, max_val)
			result[t] = max_val
		return result[-1]


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		jobLen = len(startTime)
		jobSchedule = []
		for (s, e, p) in zip(startTime, endTime, profit):
			jobSchedule.append((s, e, p))
		jobSchedule.sort(key=lambda x: (x[0], x[1], -x[2]))
		dp = {}

		def findNextJob(preE, preI):
			l = preI
			r = jobLen - 1
			if preE > jobSchedule[r][0]:
				return 0
			if (preE, preI) in dp:
				return dp[preE, preI]
			while r > l:
				m = (r + l) // 2
				if jobSchedule[m][0] < preE:
					l = m + 1
				else:
					r = m
			lastStart = jobSchedule[l][1]
			bestP = 0
			bestE = 0
			subAns = 0
			for nextJob in range(l, jobLen):
				if jobSchedule[nextJob][0] >= lastStart:
					break
				if jobSchedule[nextJob][1] >= bestE and jobSchedule[nextJob][2] <= bestP:
					continue
				if jobSchedule[nextJob][2] > bestP or (jobSchedule[nextJob][2] == bestP and jobSchedule[nextJob][1] < bestE):
					bestP = jobSchedule[nextJob][2]
					bestE = jobSchedule[nextJob][1]
				subAns = max(subAns, jobSchedule[nextJob][2] + findNextJob(jobSchedule[nextJob][1], nextJob))
			dp[preE, preI] = subAns
			return subAns
		return findNextJob(0, 0)


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		n = max(endTime)
		(dp, dicti) = ((n + 2) * [0], collections.defaultdict(list))
		for (start, end, profit) in zip(startTime, endTime, profit):
			dicti[start].append([end, profit])
		for start in range(n, -1, -1):
			dp[start] = dp[start + 1]
			if start in dicti:
				dp[start] = dp[start + 1]
				for (end, profit) in dicti[start]:
					dp[start] = max(dp[start], profit + dp[end])
		return dp[1]


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		n = len(profit)
		timeline = []
		for i in range(n):
			(timeline.append((startTime[i], n)),)
			timeline.append((endTime[i], i))
		mapping = {}
		dp = [0] * (2 * n)
		for (i, v) in enumerate(sorted(timeline)):
			if v[1] < n:
				dp[i] = max(dp[i - 1], dp[mapping[startTime[v[1]]]] + profit[v[1]])
			else:
				dp[i] = dp[i - 1]
				mapping[v[0]] = i
		return dp[-1]


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		m = {}
		new_start = []
		for (i, v) in enumerate(startTime):
			new_start.append((v, i))
			if v in m:
				m[v].append((endTime[i], profit[i]))
			else:
				m[v] = [(endTime[i], profit[i])]
		new_start = [(v, i) for (i, v) in enumerate(startTime)]
		new_start.sort()
		last = new_start[-1][0]
		dp = [0] * (last + 1)
		for v in reversed(range(last + 1)):
			if v not in m:
				dp[v] = dp[v + 1]
				continue
			maxi = -float('inf')
			for (end, profit) in m[v]:
				maxi = max(maxi, profit)
				if end < len(dp):
					val = dp[end] + profit
					maxi = max(maxi, val)
				if v + 1 < len(dp):
					maxi = max(maxi, dp[v + 1])
			dp[v] = maxi
		return dp[0]


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		(arr, length) = ([], len(startTime))
		for i in range(length):
			arr.append([startTime[i], endTime[i], profit[i]])
		arr.sort()
		ans = arr[-1][2]
		(max_start, max_prof, dp) = (arr[-1][0], arr[-1][2], {})
		dp[arr[-1][0]] = arr[-1][2]
		for i in range(length - 2, -1, -1):
			(start, end, prof) = arr[i]
			after = 0
			while end <= max_start:
				if end in dp:
					after = dp[end]
					break
				end += 1
			dp[start] = max(max_prof, prof + after)
			(ans, max_prof) = (dp[start], dp[start])
		return ans


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		jobs = []
		n = len(profit)
		for i in range(n):
			jobs.append([startTime[i], endTime[i], profit[i]])
		jobs.sort(key=lambda x: x[1])
		dp = [0 for i in range(n + 1)]
		for i in range(n):
			start = jobs[i][0]
			prof = 0
			for j in reversed(range(i)):
				if jobs[j][1] <= start:
					prof = dp[j + 1]
					break
			dp[i + 1] = max(dp[i], prof + jobs[i][2])
		return dp[n]


class Solution:

	def jobScheduling(self, startTime, endTime, profit):
		jobs = sorted(zip(startTime, endTime, profit), key=lambda v: v[0])
		heap = []
		total = 0
		for (s, e, p) in jobs:
			while heap and heap[0][0] <= s:
				(end, profit) = heappop(heap)
				total = max(total, profit)
			heappush(heap, (e, p + total))
		while heap:
			(end, profit) = heappop(heap)
			total = max(total, profit)
		return total


class Solution:

	def findprofit(self, arr):
		dp = [0 for i in range(len(arr))]
		dp[0] = arr[0][2]
		for i in range(1, len(dp)):
			including = arr[i][2]
			last_non_conflict_job = -1
			for j in range(i - 1, -1, -1):
				if arr[j][1] <= arr[i][0]:
					last_non_conflict_job = j
					break
			if last_non_conflict_job != -1:
				including += dp[last_non_conflict_job]
			dp[i] = max(dp[i - 1], including)
		return dp[-1]

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		arr = list(zip(startTime, endTime, profit))
		arr.sort(key=lambda x: x[1])
		return self.findprofit(arr)


from bisect import bisect_left

class Solution:

	def jobScheduling(self, start_times: List[int], end_times: List[int], profits: List[int]) -> int:
		(start_times, end_times, profits) = list(zip(*sorted(zip(start_times, end_times, profits))))
		n = len(start_times)
		cache = {n - 1: profits[n - 1], n: 0}

		def max_profit(i):
			if i not in cache:
				next_start = bisect_left(start_times, end_times[i])
				cache[i] = max(profits[i] + max_profit(next_start), max_profit(i + 1))
			return cache[i]
		return max_profit(0)


import bisect
from typing import List

class Solution:

	def jobScheduling(self, start: List[int], end: List[int], profit: List[int]) -> int:
		ans = []
		start_end = []
		dp = []
		for i in range(len(start)):
			start_end.append((start[i], end[i], profit[i]))
			dp.append(-1)
		start_end.sort()
		start.sort()

		def find_next_ind(curr_end):
			return bisect.bisect_left(start, curr_end)

		def recur(ind):
			if ind == len(start_end):
				return 0
			if dp[ind] != -1:
				return dp[ind]
			curr_end = start_end[ind][1]
			curr_profit = start_end[ind][2]
			new_ind = find_next_ind(curr_end)
			ans = max(curr_profit + recur(new_ind), recur(ind + 1))
			dp[ind] = ans
			return ans
		ans = 0
		recur(0)
		for res in dp:
			ans = max(ans, res)
		return ans


import bisect

class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		jobs = sorted(zip(startTime, endTime, profit))
		startTime = sorted(startTime)
		dp = [-1] * len(jobs)

		def helper(index):
			if index == len(jobs):
				return 0
			if dp[index] != -1:
				return dp[index]
			(currEnd, currProfit) = (jobs[index][1], jobs[index][2])
			newIdx = bisect.bisect_left(startTime, currEnd)
			currRes = max(currProfit + helper(newIdx), helper(index + 1))
			ans = max(dp[-1], currRes)
			dp[index] = ans
			return ans
		return helper(0)


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		events = []
		n = len(startTime)
		for i in range(n):
			events.append((startTime[i], i + 1))
			events.append((endTime[i], -i - 1))
		events.sort()
		p = 0
		for (curr, idx) in events:
			if idx > 0:
				profit[idx - 1] += p
			else:
				p = max(p, profit[-idx - 1])
		return p


import bisect
import numpy as np

class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		X = list(zip(endTime, profit, startTime))
		s = sorted(X)
		end = [x for (x, _, _) in s]
		prof = [x for (_, x, _) in s]
		start = [x for (_, _, x) in s]
		p = [0] * len(end)
		for i in range(len(end) - 1, -1, -1):
			idx = bisect.bisect(end, start[i], lo=0, hi=i)
			p[i] = idx
		dp = [0] * (len(end) + 1)
		for i in range(1, len(end) + 1):
			dp[i] = max(prof[i - 1] + dp[p[i - 1]], dp[i - 1])
		print(dp)
		return max(dp)


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		slots = {}
		slots = set(startTime + endTime)
		time = {}
		c = 0
		for s in sorted(list(slots)):
			time[s] = c
			c += 1
		for i in range(len(startTime)):
			startTime[i] = time[startTime[i]]
		tasks = collections.defaultdict(list)
		for i in range(len(endTime)):
			endTime[i] = time[endTime[i]]
			tasks[endTime[i]].append(i)
		dp = [0] * c
		for t in range(0, c):
			dp[t] = dp[t - 1]
			for job in tasks[t]:
				st = startTime[job]
				dp[t] = max(dp[t], dp[st] + profit[job])
		return max(dp)


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		line = list(set(startTime) | set(endTime))
		line.sort()
		dp = dict()
		d = dict()
		v = dict()
		for i in range(len(endTime)):
			if endTime[i] not in d:
				d[endTime[i]] = []
			d[endTime[i]].append(startTime[i])
			v[startTime[i], endTime[i]] = profit[i]
		m = 0
		for n in line:
			if n not in d:
				dp[n] = m
			else:
				dp[n] = max([m] + [dp[i] + v[i, n] for i in d[n]])
				m = max(dp[n], m)
		return dp[line[-1]]


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		N = len(startTime)
		res = sorted(zip(startTime, endTime, profit), key=lambda x: x[0])
		unzipped_res = list(zip(*res))
		startTime = unzipped_res[0]
		endTime = unzipped_res[1]
		profit = unzipped_res[2]

		@lru_cache(None)
		def solve(i):
			if i == N:
				return 0
			start = startTime[i]
			end = endTime[i]
			nextI = N
			for j in range(i + 1, N):
				if startTime[j] >= end:
					nextI = j
					break
			prof = profit[i]
			taken = solve(nextI) + profit[i]
			notTaken = solve(i + 1)
			return max(taken, notTaken)
		amt = solve(0)
		return amt


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		n = len(startTime)
		slots = []
		for i in range(n):
			slots.append([startTime[i], endTime[i], profit[i]])
		slots.sort(key=lambda x: (x[0], x[1]))
		mem = {}

		def dp(i):
			if i >= n:
				return 0
			if i == n - 1:
				mem[i] = slots[i][2]
				return mem[i]
			if i in mem:
				return mem[i]
			max_non_overlapping_val = slots[i][2]
			for j in range(i + 1, n):
				if slots[j][0] < slots[i][1]:
					continue
				max_non_overlapping_val = max(max_non_overlapping_val, slots[i][2] + dp(j))
				break
			max_non_overlapping_val = max(max_non_overlapping_val, dp(i + 1))
			mem[i] = max_non_overlapping_val
			return mem[i]
		return dp(0)


import bisect

class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		jobs = sorted(zip(startTime, endTime, profit), key=lambda t: (t[1], t[0], t[2]))
		dp = [(0, 0)]
		for (start, end, profit) in jobs:
			i = bisect.bisect_right(dp, (start, float('inf')))
			profit += dp[i - 1][1]
			if profit <= dp[-1][1]:
				continue
			if end == dp[-1][0]:
				dp[-1] = (end, profit)
			else:
				dp.append((end, profit))
		return dp[-1][1]


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		from collections import defaultdict
		times = sorted(set(startTime) | set(endTime))
		dp = [0] * len(times)
		time_id = {}
		for (i, x) in enumerate(times):
			time_id[x] = i
		start_id = defaultdict(list)
		for (i, x) in enumerate(startTime):
			start_id[x].append(i)
		for (i, x) in enumerate(times):
			if i > 0:
				dp[i] = max(dp[i], dp[i - 1])
			for j in start_id[x]:
				et = endTime[j]
				dp[time_id[et]] = max(dp[time_id[et]], dp[i] + profit[j])
		return dp[-1]


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		jobs = sorted([[startTime[i], endTime[i], profit[i]] for i in range(len(startTime))])
		mem = {}
		return self.scheduleJobs(jobs, 0, mem)

	def scheduleJobs(self, jobs, i, mem):
		if i >= len(jobs):
			return 0
		if i in mem:
			return mem[i]
		profit1 = self.scheduleJobs(jobs, i + 1, mem)
		j = i + 1
		while j < len(jobs) and jobs[j][0] < jobs[i][1]:
			j += 1
		profit2 = self.scheduleJobs(jobs, j, mem) + jobs[i][2]
		mem[i] = max(profit1, profit2)
		return mem[i]


from heapq import *

class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		jobs = sorted(zip(startTime, endTime, profit))
		heap = []
		max_profit = 0
		for job in jobs:
			while heap and heap[0][0] <= job[0]:
				max_profit = max(max_profit, heappop(heap)[1])
			heappush(heap, (job[1], max_profit + job[2]))
		for item in heap:
			max_profit = max(max_profit, item[1])
		return max_profit


class Job:

	def __init__(self, start_time, end_time, weight):
		self.start_time = start_time
		self.end_time = end_time
		self.weight = weight

	def __hash__(self):
		return hash((self.start_time, self.end_time, self.weight))

	def __eq__(self, other):
		return self.start_time == other.start_time and self.end_time == other.end_time and (self.weight == other.weight)

class WeightedIntervalSchedule:

	def __init__(self, sch):
		self.jobs = list()
		for job in sch:
			self.jobs.append(Job(job[0], job[1], job[2]))
		self.jobs_end_first = []
		self.jobs_start_first = []
		self.previous_job = len(self.jobs) * [0]
		self.memory = dict()
		self.compute_latest_job_scheduled_before()

	def getResult(self):
		return self.dp(self.jobs_end_first, len(self.jobs) - 1, self.previous_job)

	def compute_latest_job_scheduled_before(self):
		self.jobs_end_first = sorted(self.jobs, key=lambda x: x.end_time)
		indexed_jobs_start_first = [(index, job) for (index, job) in enumerate(self.jobs_end_first)]
		self.jobs_start_first = sorted(indexed_jobs_start_first, key=lambda x: x[1].start_time)
		X = len(self.jobs) * [0]
		X[0] = -1
		for i in range(1, len(self.jobs_start_first)):
			j = X[i - 1]
			while self.jobs_start_first[i][1].start_time >= self.jobs_end_first[j + 1].end_time:
				j = j + 1
			X[i] = j
		for i in range(0, len(self.jobs_start_first)):
			self.previous_job[self.jobs_start_first[i][0]] = X[i]

	def dp(self, jobs, index, previous_job):
		dp = [0] * len(jobs)
		dp[0] = jobs[0].weight
		for i in range(1, len(jobs)):
			if previous_job[i] != -1:
				dp[i] = max(dp[i - 1], jobs[i].weight + dp[previous_job[i]])
			else:
				dp[i] = max(jobs[i].weight, dp[i - 1])
		return dp[len(jobs) - 1]

class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		temp = list()
		for i in range(len(startTime)):
			temp.append([startTime[i], endTime[i], profit[i]])
		return WeightedIntervalSchedule(temp).getResult()


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		jobs = list(zip(startTime, endTime, profit))
		jobs = sorted(jobs, key=lambda x: x[1])
		dp = [0] + profit

		def search_start(i):
			nonlocal jobs
			target = jobs[i][0]
			(l, r) = (0, i)
			while l < r:
				mid = (l + r) // 2
				if jobs[mid][1] > target:
					r = mid
				else:
					l = mid + 1
			return l
		for (i, (start_time, end_time, pft)) in enumerate(jobs):
			pft_if_not_take_job = dp[search_start(i)]
			dp[i + 1] = max(dp[i], pft_if_not_take_job + pft)
		return dp[-1]


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:

		def bs(arr, l, r, target):
			while l <= r:
				m = l + (r - l) // 2
				if arr[m][0] <= target:
					l = m + 1
				else:
					r = m - 1
			return r
		dp = [[0, 0]]
		for (e, s, p) in sorted(zip(endTime, startTime, profit)):
			idx = bs(dp, 0, len(dp) - 1, s)
			if p + dp[idx][1] > dp[-1][1]:
				dp.append([e, p + dp[idx][1]])
		return dp[-1][1]


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		self.jobs = list()
		for i in range(len(startTime)):
			self.jobs.append((startTime[i], endTime[i], profit[i]))
		self.jobs.sort()
		self.memo = dict()
		return self.dfs(0)

	def dfs(self, index):
		if index == len(self.jobs):
			return 0
		if index in self.memo:
			return self.memo[index]
		res = 0
		res = max(res, self.dfs(index + 1))
		nextIndex = self.findNext(index)
		res = max(res, self.dfs(nextIndex) + self.jobs[index][2])
		self.memo[index] = res
		return res

	def findNext(self, index):
		for i in range(index + 1, len(self.jobs)):
			if self.jobs[index][1] <= self.jobs[i][0]:
				return i
		return len(self.jobs)


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		self.schedule = list(zip(startTime, endTime, profit))
		self.schedule.sort()
		self.scheduleLen = len(self.schedule)
		self.mem = [-1] * self.scheduleLen
		return self.getMaxProfit(0)

	def getMaxProfit(self, idx):
		if idx >= self.scheduleLen:
			return 0
		if self.mem[idx] != -1:
			return self.mem[idx]
		prof = 0
		endTime = self.schedule[idx][1]
		profit = self.schedule[idx][2]
		prof = max(prof, self.getMaxProfit(idx + 1))
		nextJob = self.getNextNonOverlappingJob(idx, endTime)
		prof = max(prof, profit + self.getMaxProfit(nextJob))
		self.mem[idx] = prof
		return self.mem[idx]

	def getNextNonOverlappingJob(self, i, endTime):
		while i < self.scheduleLen and self.schedule[i][0] < endTime:
			i += 1
		return i


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		T = []
		for (i, s) in enumerate(startTime):
			T.append((s, False, i))
		for (i, e) in enumerate(endTime):
			T.append((e, True, i))
		T = sorted(T)
		best = dict()
		prev = 0
		for t in T:
			(time, end, i) = t
			if end:
				curr = max(best[startTime[i]] + profit[i], prev)
			else:
				curr = prev
			best[time] = curr
			prev = curr
		return best[T[-1][0]]


from typing import List
from functools import lru_cache
from bisect import bisect

class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		intervals = sorted(zip(startTime, endTime, profit))
		n = len(intervals)

		@lru_cache(None)
		def helper(idx):
			if idx >= n:
				return 0
			(start, end, profit) = intervals[idx]
			not_take_option = helper(idx + 1)
			take_option = profit + helper(bisect(intervals, (end,)))
			return max(not_take_option, take_option)
		return helper(0)


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		jobs = []
		for idx in range(len(startTime)):
			jobs.append([startTime[idx], endTime[idx], profit[idx]])
		jobs.sort(key=lambda x: x[1])
		dp = [[0, 0]]
		for (s, e, p) in jobs:
			idx = self.bs(dp, s)
			if dp[idx - 1][1] + p >= dp[-1][1]:
				dp.append([e, dp[idx - 1][1] + p])
		return dp[-1][1]

	def bs(self, arr, val):
		l = 0
		r = len(arr) - 1
		while l < r:
			mid = (l + r) // 2
			if arr[mid][0] >= val:
				r = mid
			else:
				l = mid + 1
		return l if arr[l][0] > val else l + 1


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:

		def search(dp, end):
			(left, right) = (0, len(dp) - 1)
			while left < right:
				mid = left + (right - left + 1) // 2
				if dp[mid][0] <= end:
					left = mid
				else:
					right = mid - 1
			return left
		jobs = sorted(zip(startTime, endTime, profit), key=lambda v: v[1])
		dp = [[0, 0]]
		for (start, end, profit) in jobs:
			pos = search(dp, start)
			if dp[pos][1] + profit > dp[-1][1]:
				dp.append([end, dp[pos][1] + profit])
		return dp[-1][1]


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		if len(startTime) != len(endTime) or len(startTime) != len(profit):
			return 0
		n = len(startTime)
		combined = []
		for i in range(n):
			combined.append((endTime[i], startTime[i], profit[i]))
		combined.sort()
		dp = [0] * n
		res = 0
		for i in range(n):
			(end_i, start_i, profit_i) = combined[i]
			dp[i] = max(dp[i - 1] if i > 0 else profit_i, profit_i)
			j = self.firstPosLargerThanTarget(combined, start_i, i)
			if j > 0:
				dp[i] = max(dp[j - 1] + profit_i, dp[i])
		return dp[-1]

	def firstPosLargerThanTarget(self, combined, target, end):
		(left, right) = (0, end)
		while left + 1 < right:
			mid = (left + right) // 2
			if combined[mid][0] <= target:
				left = mid
			else:
				right = mid
		if combined[left][0] > target:
			return left
		return right


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		points = list(set(startTime + endTime))
		points.sort()
		dic = defaultdict(list)
		for (start, end, profit) in zip(startTime, endTime, profit):
			dic[end].append([start, profit])
		DP = {points[0]: 0}
		res = 0
		for i in range(1, len(points)):
			DP[points[i]] = DP[points[i - 1]]
			for (start, profit) in dic[points[i]]:
				DP[points[i]] = max(DP[points[i]], DP[start] + profit)
			res = max(res, DP[points[i]])
		return res


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		n = len(profit)
		schedule = [(startTime[i], endTime[i], profit[i]) for i in range(len(startTime))]
		schedule.sort(key=lambda x: x[1])
		dp = [0] * (n + 1)
		dp[0] = 0
		p = [0] * (n + 1)
		value = []
		value.append(0)
		for i in range(n):
			value.append(schedule[i][2])
		bs = []
		bs.append(schedule[0][1])
		p[1] = 0

		def bst(bs, x):
			h = len(bs) - 1
			l = 0
			while l <= h:
				m = (l + h) // 2
				if bs[m] == x:
					return m + 1
				elif bs[m] < x:
					l = m + 1
				else:
					h = m - 1
			return l
		for i in range(2, n + 1):
			p[i] = bst(bs, schedule[i - 1][0])
			bs.append(schedule[i - 1][1])
		for i in range(1, n + 1):
			dp[i] = max(dp[i - 1], dp[p[i]] + value[i])
		return dp[-1]


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		A = sorted(zip(startTime, endTime, profit))
		n = len(A)

		def find_next_starting_point(cur_starting_point, start_time):
			if cur_starting_point >= n:
				return cur_starting_point
			(left, right) = (cur_starting_point, n - 1)
			while left + 1 < right:
				mid = left + (right - left) // 2
				if A[mid][0] < start_time:
					left = mid
				else:
					right = mid
			if A[left][0] >= start_time:
				return left
			if A[right][0] >= start_time:
				return right
			return right + 1
		cache = {n: 0}

		def find_max_profit(i):
			if i in cache:
				return cache[i]
			next_start = find_next_starting_point(i + 1, A[i][1])
			with_cur_task = A[i][2] + find_max_profit(next_start)
			without_cur_task = find_max_profit(i + 1)
			cache[i] = max(with_cur_task, without_cur_task)
			return cache[i]
		return find_max_profit(0)

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		A = sorted(zip(endTime, startTime, profit))
		n = len(A)
		cache = [0] * (n + 1)

		def find_closest_ending_point(cur_ending_point, end_time_limit):
			if cur_ending_point < 0:
				return 0
			(left, right) = (0, cur_ending_point)
			while left + 1 < right:
				mid = left + (right - left) // 2
				if A[mid][0] <= end_time_limit:
					left = mid
				else:
					right = mid
			if end_time_limit >= A[right][0]:
				return right + 1
			if end_time_limit >= A[left][0]:
				return left + 1
			return left
		for i in range(1, n + 1):
			index = find_closest_ending_point(i - 2, A[i - 1][1])
			cache[i] = max(cache[i - 1], cache[index] + A[i - 1][2])
		return cache[n]


from functools import lru_cache

class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		if not startTime or not endTime or (not profit):
			return 0
		intervals = list(zip(startTime, endTime, profit))
		intervals.sort(key=lambda x: x[0])

		def find_next_idx_binary_search(left, right, time):
			while left < right:
				mid = left + (right - left) // 2
				if intervals[mid][0] >= time:
					right = mid
				else:
					left = mid + 1
			return left

		@lru_cache(maxsize=None)
		def helper(idx):
			if idx == len(intervals) or idx < 0:
				return 0
			j = find_next_idx_binary_search(idx + 1, len(intervals), intervals[idx][1])
			return max(helper(j) + intervals[idx][2], helper(idx + 1))
		return helper(0)


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		lis = []
		dp = []
		for i in range(len(startTime)):
			lis += [[startTime[i], endTime[i], profit[i]]]
		lis = sorted(lis, key=lambda x: x[0])
		dp += [lis[-1][2]]
		for i in range(len(lis) - 2, -1, -1):
			cur = lis[i][2]
			for j in range(i + 1, len(lis)):
				if lis[j][0] >= lis[i][1]:
					cur = lis[i][2] + dp[i - j]
					break
			dp += [max(cur, dp[-1])]
		return dp[-1]


from functools import lru_cache

class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		list_jobs = sorted(zip(startTime, endTime, profit))

		@lru_cache(maxsize=None)
		def find(i=0):
			if i >= len(list_jobs):
				return 0
			l = i + 1
			r = len(list_jobs) - 1
			j = len(list_jobs)
			while l <= r:
				middle = (l + r) // 2
				if list_jobs[middle][0] < list_jobs[i][1]:
					l = middle + 1
				else:
					r = middle - 1
					j = middle
			return max(list_jobs[i][2] + find(j), find(i + 1))
		return find()


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		n = len(profit)
		line = list(zip(startTime, endTime, profit))
		line.sort(key=lambda x: x[1])
		dp = [0] * n
		dp[0] = line[0][2]
		for i in range(n):
			prev_profit = 0
			(left, right) = (0, i - 1)
			while left <= right:
				mid = (left + right) // 2
				if line[i][0] < line[mid][1]:
					right = mid - 1
				else:
					prev_profit = dp[mid]
					left = mid + 1
			dp[i] = max(dp[i - 1], prev_profit + line[i][2])
		return dp[-1]


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		jobs = []
		for i in range(len(startTime)):
			jobs.append([startTime[i], endTime[i], profit[i]])
		jobs = sorted(jobs, key=lambda x: x[1])
		dp = [0 for i in range(len(jobs))]
		dp[0] = jobs[0][2]

		def search(target):
			(l, r) = (0, len(jobs))
			while l < r:
				mid = l + (r - l) // 2
				if jobs[mid][1] < target:
					l = mid + 1
				else:
					r = mid
			return l
		for i in range(1, len(jobs)):
			(start, end, profit) = jobs[i]
			idx = search(start)
			if jobs[idx][1] == start:
				prev_best = dp[idx]
			elif jobs[idx - 1][1] < start:
				prev_best = dp[idx - 1]
			else:
				prev_best = 0
			dp[i] = max(dp[i - 1], profit + prev_best)
		return dp[-1]


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:

		def binary_search(intervals, index):
			start = 0
			end = index
			while start < end:
				mid = (start + end) // 2
				if intervals[mid][1] > intervals[index][0]:
					end = mid
				else:
					start = mid + 1
			return start - 1
		intervals = []
		for i in range(len(startTime)):
			intervals.append((startTime[i], endTime[i], profit[i]))
		intervals.sort(key=lambda i: i[1])
		dp = [0] * len(intervals)
		for i in range(len(intervals)):
			profit_if_i_inlcuded = intervals[i][2]
			k_th = binary_search(intervals, i)
			if k_th != -1:
				profit_if_i_inlcuded += dp[k_th]
			dp[i] = max(dp[i - 1], profit_if_i_inlcuded)
		return max(dp)


class Job:

	def __init__(self, start_time, end_time, weight):
		self.start_time = start_time
		self.end_time = end_time
		self.weight = weight

	def __hash__(self):
		return hash((self.start_time, self.end_time, self.weight))

	def __eq__(self, other):
		return self.start_time == other.start_time and self.end_time == other.end_time and (self.weight == other.weight)

class WeightedIntervalSchedule:

	def __init__(self, sch):
		self.jobs = list()
		for job in sch:
			self.jobs.append(Job(job[0], job[1], job[2]))
		self.jobs_end_first = []
		self.jobs_start_first = []
		self.X = len(self.jobs) * [0]
		self.previous_job_mapping = dict()
		self.memory = dict()
		self.compute_latest_job_scheduled_before()

	def getResult(self):
		return self.dp(self.jobs_end_first, len(self.jobs) - 1, self.previous_job_mapping)

	def compute_latest_job_scheduled_before(self):
		self.jobs_start_first = sorted(self.jobs, key=lambda x: x.start_time)
		self.jobs_end_first = sorted(self.jobs, key=lambda x: x.end_time)
		self.X[0] = -1
		for i in range(1, len(self.jobs_start_first)):
			j = self.X[i - 1]
			while self.jobs_start_first[i].start_time >= self.jobs_end_first[j + 1].end_time:
				j = j + 1
			self.X[i] = j
		for i in range(0, len(self.jobs_start_first)):
			self.previous_job_mapping[self.jobs_start_first[i]] = self.X[i]

	def dp(self, jobs, index, mapping):
		current_job = jobs[index]
		profit_including_current_job = current_job.weight
		profit_excluding_current_job = 0
		if index == 0:
			return profit_including_current_job
		if index in self.memory:
			return self.memory[index]
		if mapping[jobs[index]] != -1:
			profit_including_current_job += self.dp(jobs, mapping[jobs[index]], mapping)
		profit_excluding_current_job = self.dp(jobs, index - 1, mapping)
		result = max(profit_including_current_job, profit_excluding_current_job)
		self.memory[index] = result
		return result

class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		temp = list()
		for i in range(len(startTime)):
			temp.append([startTime[i], endTime[i], profit[i]])
		return WeightedIntervalSchedule(temp).getResult()


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		jobs = sorted(zip(startTime, endTime, profit), key=lambda v: v[1])

		def search(idx):
			e_time = jobs[idx][0]
			(l, r) = (0, idx - 1)
			while l <= r:
				mid = (r - l) // 2 + l
				if jobs[mid][1] <= e_time:
					if jobs[mid + 1][1] <= e_time:
						l = mid + 1
					else:
						return mid
				else:
					r = mid - 1
			return -1

		def find(idx):
			e_time = jobs[idx][0]
			(l, r) = (0, idx)
			while l < r:
				mid = (r - l) // 2 + l
				if jobs[mid][1] <= e_time:
					l = mid + 1
				else:
					r = mid
			return l - 1
		dp = [0] * len(jobs)
		dp[0] = jobs[0][2]
		for i in range(1, len(jobs)):
			profit = jobs[i][2]
			j = find(i)
			if j != -1:
				profit += dp[j]
			dp[i] = max(dp[i - 1], profit)
		print(dp)
		return dp[-1]


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		n = len(startTime)
		stack = [0 for _ in range(n)]
		for i in range(len(startTime)):
			stack[i] = [startTime[i], endTime[i], profit[i]]
		stack = sorted(stack, key=lambda x: x[1])
		print(stack)
		dp = [[0, 0]]
		for (s, e, p) in stack:
			idx = self.binarySearch(dp, s)
			if dp[idx][1] + p > dp[-1][1]:
				dp.append([e, dp[idx][1] + p])
		return dp[-1][1]

	def binarySearch(self, dp, s):
		(i, j) = (0, len(dp))
		while i < j:
			mid = i + (j - i) // 2
			if dp[mid][0] == s:
				return mid
			elif dp[mid][0] > s:
				j = mid
			else:
				i = mid + 1
		if i == len(dp):
			return i - 1
		elif dp[i][0] > s:
			return i - 1
		else:
			return i


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		jobs = list(zip(startTime, endTime, profit))
		jobs.sort(key=lambda x: x[1])
		n = len(jobs)

		def binarySearchForLastDisjointInterval(interval: List[int]) -> int:
			(s1, e1) = interval
			(l, r) = (0, n - 1)
			while l <= r:
				mid = (l + r) // 2
				(s2, e2) = (jobs[mid][0], jobs[mid][1])
				if s1 >= e2:
					l = mid + 1
				else:
					r = mid - 1
			return r

		def getLastDisjointIntervals() -> List[int]:
			last_disjoint_intervals = [None] * n
			for i in range(n):
				interval = [jobs[i][0], jobs[i][1]]
				last_disjoint_intervals[i] = binarySearchForLastDisjointInterval(interval)
			return last_disjoint_intervals
		last_disjoint_intervals = getLastDisjointIntervals()
		dp = [0] * n
		dp[0] = jobs[0][2]
		for i in range(1, n):
			profit_not_take = dp[i - 1]
			profit_take = jobs[i][2]
			j = last_disjoint_intervals[i]
			if j != -1:
				profit_take += dp[j]
			dp[i] = max(profit_not_take, profit_take)
		return dp[n - 1]


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		comb = []
		dd = dict()
		for i in range(len(startTime)):
			comb.append((startTime[i], endTime[i], profit[i]))
		comb.sort()
		print(comb)
		l = len(comb)

		def returnIdx(idx, l, val):
			while idx < l:
				mid = idx + (l - idx) // 2
				if comb[mid][0] < val:
					idx = mid + 1
				else:
					l = mid
			return idx

		def maxProfit(jobidx):
			if jobidx == l:
				return 0
			if jobidx in dd:
				return dd[jobidx]
			ans = 0
			ans = max(ans, maxProfit(jobidx + 1))
			ans = max(ans, comb[jobidx][2] + maxProfit(returnIdx(jobidx, l, comb[jobidx][1])))
			dd[jobidx] = ans
			return ans
		return maxProfit(0)


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		self.jobs = list()
		for i in range(len(startTime)):
			self.jobs.append((startTime[i], endTime[i], profit[i]))
		self.jobs.sort()
		self.memo = dict()
		return self.dfs(0)

	def dfs(self, index):
		if index == len(self.jobs):
			return 0
		if index in self.memo:
			return self.memo[index]
		res = 0
		res = max(res, self.dfs(index + 1))
		nextIndex = self.findNext(index)
		res = max(res, self.dfs(nextIndex) + self.jobs[index][2])
		self.memo[index] = res
		return res

	def findNext(self, index):
		left = index + 1
		right = len(self.jobs)
		target = self.jobs[index][1]
		while left < right:
			mid = (left + right) // 2
			if self.jobs[mid][0] < target:
				left = mid + 1
			else:
				right = mid
		return left


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		dp = {}
		interval = []
		for i in range(len(startTime)):
			interval.append((endTime[i], startTime[i], profit[i]))
		interval.sort()
		ans = 0
		for (j, i, p) in interval:
			index = self.find_previous_end(interval, i)
			dp.setdefault(index, 0)
			dp[j] = max(dp[index] + p, ans)
			ans = max(ans, dp[j])
		return ans

	def find_previous_end(self, nums, target):
		(l, r) = (0, len(nums))
		while l + 1 < r:
			mid = (l + r) // 2
			if nums[mid][0] > target:
				r = mid
			else:
				l = mid
		if nums[r][0] <= target:
			return nums[r][0]
		if nums[l][0] <= target:
			return nums[l][0]
		return 0


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		n = len(startTime)
		arr = [(endTime[i], startTime[i], profit[i]) for i in range(n)]
		arr.sort()
		dp = [0 for x in range(n)]
		dp[0] = arr[0][2]
		for i in range(1, n):
			(e, s, p) = (arr[i][0], arr[i][1], arr[i][2])
			(bs, be) = (0, i - 1)
			ridx = -1
			while bs <= be:
				m = (bs + be) // 2
				if arr[m][0] > s:
					be = m - 1
				else:
					ridx = max(ridx, m)
					bs = m + 1
			if ridx == -1:
				dp[i] = max(dp[i - 1], p)
			else:
				dp[i] = max(dp[i - 1], dp[ridx] + p)
		return max(dp)


class Solution:

	def next_index(self, arr, i, target):
		left = 0
		right = i
		if i < 0:
			return -1
		mid = left
		while left < right:
			mid = (left + right + 1) // 2
			if arr[mid][1] <= target:
				left = mid
			elif arr[mid][1] > target:
				right = mid - 1
		return left if arr[left][1] <= target else -1

	def solve(self, i, arr):
		if i < 0:
			return 0
		if i in self.dp:
			return self.dp[i]
		x = self.solve(i - 1, arr)
		y = 0
		ind = self.next_index(arr, i - 1, arr[i][0])
		y = self.solve(ind, arr) + arr[i][2]
		self.dp[i] = max(x, y)
		return self.dp[i]

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		self.dp = {}
		arr = []
		for i in range(len(startTime)):
			arr.append((startTime[i], endTime[i], profit[i]))
		arr.sort(key=lambda x: x[1])
		ans = self.solve(len(profit) - 1, arr)
		return ans


class Solution:

	def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
		jobs = []
		for (s, e, p) in zip(startTime, endTime, profit):
			jobs.append([s, e, p])
		jobs.sort(key=lambda x: x[0])
		memo = [0] * len(jobs)

		def recur(i):
			if i >= len(jobs):
				return 0
			if memo[i] > 0:
				return memo[i]
			else:
				pro = 0
				(l, r) = (i + 1, len(jobs))
				while l < r:
					mid = (l + r) // 2
					if jobs[mid][0] < jobs[i][1]:
						l = mid + 1
					else:
						r = mid
				pro = max(recur(i + 1), recur(l) + jobs[i][2])
				memo[i] = pro
				return pro
		return recur(0)