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

Difficulty: interview

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:
        
        # max profit ending at time t
        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):
                # end, pro = dp[i]
                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:
        # TLE
        # jobs = sorted(zip(startTime, endTime, profit), key=lambda v: v[1])
        # dp = defaultdict(int)
        # dp[0] = 0
        # #find the max profit before time i
        # def find(i):
        #     tmp = []
        #     for time in dp:
        #         if time<=i:
        #             tmp.append(dp[time])
        #     return max(tmp)
        # for s, e, p in jobs:
        #     dp[e] = max(find(e),find(s)+p)
        # return max(list(dp.values()))
        
        jobs = sorted(zip(startTime, endTime, profit), key=lambda v: v[1])
        # time 0: profit 0
        dp = [(0,0)]
        
        #find the max profit before time i
        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
        #[1,2,3] target= 4
        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:
        '''
        diff from max intervals. 
        Sort by Start Time (dont do the greedy sort by earliest finish time)
        Choose it or dont. 
        Always choose it if it doesnt interfere with the next one. 
        you can binary search the end time in the start times to find the next available start times you can take. 
        
        Have 3 solutions.
        '''
       
        # sort by start times
        res = sorted(zip(startTime, endTime, profit), key=lambda x: x[0])
        # unzip it now!
        unzipped_res = list(zip(*res))
        startTime = unzipped_res[0]
        endTime = unzipped_res[1]
        profit = unzipped_res[2]
        
        #return self.topDown(startTime, endTime, profit)
        return self.backwardDP(startTime, endTime, profit)
        # return self.forwardDP(startTime, endTime, profit)
    
    # TOP DOWN COMPLETED.
    def topDown(self, startTime, endTime, profit):
        N = len(startTime)
        
        # Only memoizing one param
        '''
        Thought I would need to do the other params like 
        endTime or maxProfit but dont have to because 
        parent call does not have to communicate to child recursive calls
        to help child recursive calls to achieve max. Since we
        dont need parent-child communication, we can get away with 
        passing very little info to child through its function params.
        '''
        @lru_cache(None)
        def solve(i):
            
            if i == N:
                return 0
            
            # either take or dont
            start = startTime[i]
            end = endTime[i]
            
            # you can skip to the index that has a start time ahead of 
            # end time -> so that you dont have to 
            # pass along endtime in memtable? 
            
            nextI = N
            
            # CAN USE BINARY SEARCH HERE!
            for j in range(i+1, N):
                if startTime[j] >= end:
                    nextI = j
                    break
                    
            prof = profit[i]
            
            # take it
            taken = solve(nextI) + profit[i]
            
            # dont take:
            notTaken = solve(i+1)
            # print(\"nextI, TAKEN AND NOT TAKEN ARE\", i,nextI, taken, notTaken)
            return max(taken, notTaken)
        
        amt = solve(0)
        return amt
            
    def backwardDP(self, startTime, endTime, profit):      
        from bisect import bisect_left
        
        # Bottom Up.
        '''
        
        So the states I need is 
        max profit achieved at each index. 
        then we binary search to the right an index we can use to include
        in our max profit!
        
        and process backwards like that!
        
        OPT[i] = max(Take, DontTake)
                    OPT[i`] + profit[i], OPT[i-1]
                    
        
        '''
        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]
            
            # Take operation
            # find the end index!
            
            # endI = bisect_left(end, startTime)
            # if endI < 
            freeK = N
            '''
            Linear search that leads to O(N^2)
            for k in range(i+1, N):
                if end <= startTime[k]:
                    freeK = k
                    break    
            '''
            # Has to be bisect_left not bisect_right!
            freeK = bisect_left(startTime, end)
            take = profit[i] + OPT[freeK]
            dontTake = OPT[i+1]
            OPT[i] = max(take, dontTake)
        return OPT[0]
    
    # COULD NOT DO FORWARD VERY HARD!
    def forwardDP(self, startTime, endTime, profit):
        '''
        Ok look at idx 0
            -> Is there a way to do it NlogN?
            -> find all intervals to right that dont intersect with us!
            -> add it in. 
            
        Is this the brute force solution or what does the brute force 
        solution look like?

        Actaully this one is very difficult
        '''
        N = len(startTime)
        OPT = [profit[i] for i in range(N)]
        
        for i in range(N):
            # find all intervals ahead of us! 
            # and add us in.
            
            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:
        # sort intervals by their endTime
        intervals = sorted(zip(startTime, endTime, profit), key=lambda x: (x[1], x[2]))
        N = len(profit)
        # bottom up solutions: (profit, endtime, index)
        dp = [(0, 0, 0)]
        
        for idx, (s, e, p) in enumerate(intervals):
            nonoverlapping_idx = self.find_nonoverlapping_interval(dp, s + 0.1)
            # print(idx, nonoverlapping_idx, s)
            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])
        
        # print(dp)
        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
        
        # print(dp, l_idx, r_idx, start)
        
        # using binary search
        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
        
        # print(dp, l_idx, r_idx, start)
        
        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))
        #     print(dp, last_start, start)
        # print(dp)
        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])
        #print(times)
        
        dp[0]=times[0][2]
        
        for i in range(1,n):
            prof = times[i][2]
            binInd = self.binsearch(times, times[i][0], -1, i)
            #print(binInd)
            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:
        '''
        Refer to Eva Tardos's 'Algorithm Design' - 6.1 Weighted Interval Scheduling
        
        First post in the discuss section explains the same approach
        
        Steps
        ------
        1. Sort and order jobs by the end time - O(n logn)
        
        2. Build a most_recent array with most_recent[j] being the index of the most recent disjoint job - O(n logn)
           ** use binary search to build this array ** 
           
        3. Calculate profit for each position using the relation - O(n)
           ** dp_profits[j] = max(profits[j] + dp_profits[previous[j]], dp_profits[j-1]) **
        '''
        
        # zip and order jobs by end time
        jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])
        
        '''
        for each job in jobs find the most recent disjoint
        this is nothing but finding the index of the floor of each start time in the sorted end times
        i.e. for each start time, finding the index of greatest end time less than or equal to start time
        
        if the floor is not present the value returned would be -1
        '''
        def binary_search(val: int):
            '''
            Try doing a dry run with test cases before implementing
            
            Always choose one test value in the left of mid, one in the right and one for each boundar condition.
            Refer to vscode playground floor.py
            '''
            nonlocal jobs
            
            # boundary conditions - note job = (start_time, end_time, profit)
            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])
        
        '''
        Calculate profit for each job using recurrence relation and return the last value.
        
        
        '''
        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

'''
n份工作薪水不同，开始时间和结束时间不同，找到最大的收益，时间不能冲突。

背包问题，工作可以做或者不做，做时选择下一个不冲突的工作继续。
'''

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():
            # dp[end] = max(dp[end-1],dp[last_not_conflict] + profit))
            # end有多个，用坐标代替
            # sort(end)
            # dp[i] = max(dp[i-1],dp[last_not_conflict] + profit))

            # 二分加速

            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]
                # 再判断一次，防止0
                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 heapq import heappush, heappop
from sortedcontainers import SortedList
class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        # sort by the starting times
        lst = sorted(zip(startTime, endTime, profit))
        maxprofit, tempstck = 0, SortedList()
        # tempstck -> [(profitval, -endtime)]
        # maxheap -> -maxprofit
        for i in range(len(lst)):
            curr_strt, curr_end, curr_price = lst[i]
            while tempstck and -tempstck[-1][0] <= curr_strt:
                # pop and insert into max heap
                maxprofit = max(tempstck.pop()[1], maxprofit)
            # now do dp
            curr_maxprofit = maxprofit + curr_price
            tempstck.add((-curr_end, curr_maxprofit))
            # don't update maxprofit now because we are not sure whether the next starting price would be greater than current ending price which
            # is why we add it to the temp stack to process it later
        return max(maxprofit, *(i[1] for i in tempstck))

#[Runtime: 584 ms, faster than 74.95%] DP, BinarySearch
#O(NlogN)
#sort by endtime, iterate each job from earlier-end to latest-end
#f(i): the maximum profit if we can take job[0~i]
#f(-1) = 0
#f(i) = max{ f(i-1), f(j) + profit[i] } for first j s.t. endTime[j] <= startTime[i]
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 #search in endTime[0~i-1]
            dp[i] = max(dp[i-1], dp[j] + profit[i]) #j=-1 if not found, and dp[-1] is 0
        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)
        # for job in jobs:
            # print(job.start, ', ', job.end, ', ', job.profit)
        dp = [0] * len(jobs)
        dp[0] = jobs[0].profit
        for i in range(1, len(jobs)):
            dp[i] = jobs[i].profit
            # find the job whose end time is smaller than job i's start time
            index = self.findPreviousJob(jobs, i)
            if jobs[index].end <= jobs[i].start:
                dp[i] += dp[index]
            '''
            index = -1
            for j in range(i):
                if jobs[j].end <= jobs[i].start:
                    index = j
                else:
                    break
            if index >= 0:
                dp[i] = dp[index] + dp[i]
            '''
            dp[i] = max(dp[i-1], dp[i])
            # print(dp)
        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:
        
       # (1,3,50),(2,4,10),(3,5,40),(3,6,70)
        
        
        
        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])
            #print(dp)
            p=binarysearch(i)
            #print(p)
            #for j in range(i):
            if l[p][1]<=l[i][0]:
                dp[i]=max(dp[i],dp[p]+l[i][2])
              #  else:
               #     break
           # print(dp)
        #    ma=max(ma,dp[i])
       # print(dp)
        return dp[-1]


class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        '''
            take timeslot list: [(s1,f1)...(si, fi)]
            sort by finish time, build dp array
            dp[0] = 0
            dp[i] = max(take i, dont take i)
                  = max(first non overlapping j -> dp[j] + profit[i], dp[i-1]) 
                  
            startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
            
            
            timeslots [(0, 1, 3) (1, 2, 4) (2, 3, 5) (3, 3, 6)]
            dp [0, 50, 50, 90, 120]
        
        '''
        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]



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] * (n+1)
       
        for i in range(n):
            dp[i+1] = dp[i]
            l = 0
            r = i-1
            while l <= r:
                mid = (l+r) // 2
                if jobs[mid][1] <= jobs[i][0]:
                    l = mid + 1
                else:
                    r = mid - 1 
            dp[i+1] = max(dp[i+1], dp[l]+jobs[i][2])
        return dp[n]
    
    
        
            
            


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:
        #用空间存在startTime开始前最大的profit
        #像找零钱一样写的话，会很慢
#         jobs = []
#         for i in range(len(startTime)):
#             jobs.append([startTime[i], endTime[i], profit[i]])
#         jobs.sort(key = lambda x:x[1])
        
#         dict1 = {}
#         for job in jobs:
#             if job[1] not in dict1:
#                 dict1[job[1]] = [job]
#             else:
#                 dict1[job[1]].append(job)
#         tail = jobs[-1][1]
#         dp = [0 for _ in range(tail + 1)]
        
#         for i in range(1, len(dp)):
#             dp[i] = dp[i-1]
#             if i in dict1:
#                 for job in dict1[i]:
#                     startTime = job[0]
#                     dp[i] = max(dp[i], dp[startTime] + job[2])
#         #print(dp)
#         return dp[-1]

        #因为仅有做决定的点有用，所以我们不需要把所有的点取下来，仅需要存每次做决定产生的最大值
        #就像找零钱，每次做决定的时候，找dp[cur - value]
        #但是因为我们只存了稀疏的链表结构，需要在存的结果中找那个对应的dp[cur - value]的点
        
        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))
        
        #print(sd)
        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()
        # print(jobs)
        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])
        # print(dp)
        return dp[-1]
    
    def get_prev_idx(self, target, arr):
        # find the greatest number smaller or equal to target in sorted arr
        # print('---')
        # print(target)
        # print(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
        # if arr[l] <= target:
        #     # print(arr[l])
        #     return arr[l]
        # print(arr[l-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=[[] for i in range(n)]
        
        for i in range(n):
            table[i]=[startTime[i],endTime[i],profit[i]]
        table.sort(key = lambda x:x[1])
        print(table)'''
        
        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)
            #print(loca,table[i])
            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))
        #print(temp)
        #return 0
        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])
                
        # print(temp)
        # print(ans)        
        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]


class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        
        # max profit ending at time t
        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 i in range(len(dp)-1, -1,-1):
                end, pro = dp[i]
                if end <= s:
                    doTaskProf = pro + p
                    break
            if doTaskProf > noTaskProf:
                dp.append((e, doTaskProf))
        return dp[-1][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)

        # either take the job or don't take the job
        # dp[i] = max(dp[i-1], dp[k] + p) for j[k][e] <= j[i][s]
        N = len(jobs)
        dp = [0 for _ in range(N)]

        dp[0] = jobs[0][2]

        # TODO: might have to rethink just a little bit here.
        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]) # take the profit
            else: # if I can't find anything then just take the max.
                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
            # arr[m].end <= start
            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_start(boundary) ....... floor_end
            #     [start                        end]   <- need check
            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])
        #print(jobs)

        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:
        n=len(startTime)
        table=[[] for i in range(n)]
        
        for i in range(n):
            table[i]=[startTime[i],endTime[i],profit[i]]
        table.sort(key = lambda x:x[1])
        print(table)
        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)
            #print(loca,table[i])
            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:
        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 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:
        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]) # sorted by endTime
        T = intervals[-1][1] # largest time

        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]
                
                
                # dp 
                #    0 1 2 ....6


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]:
                    #print(j,dp[i])
                    dp[i] = max(dp[i-1],dp[j[0]]+j[1],dp[i])
            else:
                dp[i]=dp[i-1]
        #print(dp)
        return dp[nn]
            


class Solution:
    def jobScheduling(self, startTime, endTime, profit):
        jobs = sorted(zip(startTime, endTime, profit), key=lambda v: v[1])
        print(jobs)

        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

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)

        # either take the job or don't take the job
        # dp[i] = max(dp[i-1], dp[k] + p) for j[k][e] <= j[i][s]
        N = len(jobs)
        dp = [0 for _ in range(N)]

        dp[0] = jobs[0][2]

        # TODO: might have to rethink just a little bit here.
        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]) # take the profit
            else: # if I can't find anything then just take the max.
                dp[i] = max(job[2], dp[i])
        
        return dp[N-1]





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]
        
        
    '''
    [[1,3],[2,4],[3,5],[3,6]] [50,10,40,70]
    
    [0,-i,-i,50,50,90,120]
    
    startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
    [0,0,0,20,20,20,90,90,90,150,150]
    
    [1,2,3,3]
    [3,4,5,6]
    [50,10,40,70]
  [0,0,0,50,50,90,120] 
    dp = []
    
    
    [47,13,28,16,2,11]
    [48,35,48,26,21,39]
    [11,13,2,15,1,1]
    
    [1,15,15,15,17]
    '''


class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        l=len(startTime)
        sep=list(zip(endTime,startTime,profit))
        # for i in range(l):
        #     sep.append(())
        sep=sorted(sep)
       # print(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
      #  print(dp)
        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]:
                    # print(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]))
        
        # print(jobSchedule)
        
        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:
    # DP bottom-up working from end to start
    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])
        #print(dp)
        return dp[n]

class Solution:
    def jobScheduling(self, startTime, endTime, profit):
        jobs = sorted(zip(startTime, endTime, profit), key=lambda v: v[0])
        #Heap store (endTime, profitSoFar)
        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] # dp[i] -> profit till ith job (we know jobs are sorted by finish time)
        
        # now we start filling dp from index 1, cause 0 has been taken care of
        for i in range(1,len(dp)):
            including = arr[i][2] # if we decide to include ith job's profit , we have to do some checks 
            
            last_non_conflict_job = -1
            for j in range(i-1,-1,-1): # check all the previous jobs and find the one that doesnt conflict with this current ith job, we traverse in reverse to find the last one that doesnt conflict
                if arr[j][1]<=arr[i][0]: # if end time of jth(previous ones) is less that start time of current ,, then we are good to go
                    
                    last_non_conflict_job = j # we found the job
                    break # breaking here is very important otherwise we will not find the last job but the first job
            
            if last_non_conflict_job!=-1: # that means we know the previous job and we can now add our current job in it
                including += dp[last_non_conflict_job]
                
            dp[i] = max(dp[i-1],including) # dp[i] has two options, to take ith job or to not take ith job, we do whichever is maximum
        return(dp[-1])
                    
                    
        
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        # arr = [[startTime[i],endTime[i],profit[i]] for i in range(len(startTime))]
        arr = list(zip(startTime,endTime,profit))
        arr.sort(key=lambda x:x[1]) # sort by finish time
        
        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)


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]

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


# dynamic programming + binary search
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:
        
        
        # tps = sorted(zip(endTime,startTime, profit))
        # print (tps)
        # return 0
        events = []
        n = len(startTime)
        for i in range(n):
            events.append((startTime[i], i + 1))            
            events.append((endTime[i], -i - 1))
        
        events.sort()
        # print (events)
        
        p = 0
        for (curr, idx) in events:
            if idx > 0:
                profit[idx - 1] += p
            else:
                p = max(p, profit[-idx - 1])
            # print (curr, p)
        return p


import bisect
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
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:
        jobs = []
        for i in range(len(profit)):
            jobs.append([startTime[i], endTime[i], profit[i]])
        
        srt = sorted(jobs, key=lambda x: x[1])
        print(srt)
        maxp = [j[2] for j in srt]
        n = len(profit)
        for i in range(1,n):
            for j in range(i-1, -1, -1):
                
                if srt[j][1] <= srt[i][0]:
                    maxp[i] = max(srt[i][2] + maxp[j], maxp[i-1])
                    break
            maxp[i] = max(maxp[i-1], maxp[i])
        print(maxp)
        return maxp[-1]

class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        '''
        diff from max intervals. 
        
        either take or dont take a certain interval.
        
        then do max
        Do top down then bottom up. 
        
        Greedy -> earliest finishing time. 
        
        Sort by finishing time. 
        Choose it or dont. 
        Always choose it if it doesnt interfere with the next one. 
        
        you can binary search the end time in the start times to find the next available start times you can take. 
        
        
        So DP[i] -> max profit after processing interval i. 
        
        '''
        N = len(startTime)
        
        
        # sort by start times
        
        res = sorted(zip(startTime, endTime, profit), key=lambda x: x[0])
        # print(\"res\", res)
        
        # unzip it now!
        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
            
            # either take or dont
            start = startTime[i]
            end = endTime[i]
            
            # you can skip to the index that has a start time ahead of 
            # end time -> so that you dont have to 
            # pass along endtime in memtable? 
            
            nextI = N
            
            for j in range(i+1, N):
                
                if startTime[j] >= end:
                    nextI = j
                    break
            
            prof = profit[i]
            
            # take it
            taken = solve(nextI) + profit[i]
            
            # dont take:
            notTaken = solve(i+1)
            # print(\"nextI, TAKEN AND NOT TAKEN ARE\", i,nextI, taken, notTaken)
            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)] # (endtime, max profit till this endtime) 
        # profit and endtime will both be strictly increasing
        for start, end, profit in jobs:
            i = bisect.bisect_right(dp, (start, float('inf'))) # dp[i - 1][0] <= end
            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):
        '''
        select current job, and push i after the end time of jobs[i]
        or
        skip current job, and push i += 1
        '''
        if i >= len(jobs):
            return 0
        if i in mem:
            return mem[i]
        
        # skip current job, and push i += 1
        profit1 = self.scheduleJobs(jobs, i + 1, mem)
        
        # select current job, and push i after the end time of jobs[i]
        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
            
        



# This class represents a job = [start-time, end-time, weight]
class Job:
    def __init__(self, start_time, end_time, weight):
        self.start_time = start_time
        self.end_time = end_time
        self.weight = weight

    #overriding hashcode and equals to use the Job object as a key in dict
    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]
        # Memoization will be done using this memory dict
        self.memory = dict()
        #computing the previous mappings
        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):
        
        # Sorting the jobs in non decreasing order of end_time - O(nlogn)
        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)]
        # Sorting the jobs in non decreasing order of start_time - O(nlogn)
        self.jobs_start_first = sorted(indexed_jobs_start_first, key=lambda x: x[1].start_time)

        # This list X will store the index of the previous job in jobs_end_first
        X = len(self.jobs) * [0]
        X[0] = -1

        # The time complexity of this method is O(n) as the statement inside the while loop
        # is only called once for each index
        # We use the intution that the latest job for the current job will be greater than or 
        # equal to the latest job for the preious job
        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

        # We now map the respective job to its index in jobs_end_first.
        # O(n)        
        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
        # print(dp)
        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)
            
        # print(dp)    
        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:
        # Approach: dfs with memoization
        
        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:
        # sort the set of all start and end
        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
            #print(\"index: {}, time: {}, curr: {}\".format(i, 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]] # end_time, profit
        for start, end, profit in jobs:
            pos = search(dp, start)
            # print(pos, dp, end)
            if dp[pos][1] + profit > dp[-1][1]:
                dp.append([end, dp[pos][1] + profit])
        return dp[-1][1]

# dp[i] :max profit if take the ith job
# dp[i] = max(0, dp[j] + profit[i] if endTime[j] <= startTime[i]) for j < i
# return max(dp)

#DP + Binary Search
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:
    # Without cache, O(2^n log n) time, O(1) space; with cache, O(n x log n) time, O(n) space
    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
            # left < start_time
            if A[right][0] >= start_time:
                return right
            # right < start_time
            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)

    # O(n x log n) time, O(n) space
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        
        A = sorted(zip(endTime, startTime, profit))
        n = len(A)
        
        # The biggest profit as of the ith task
        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
            # end_time_limit < right
            if end_time_limit >= A[left][0]:
                return left + 1
            # end_time_limit < left
            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))
        # sorted by start-time
        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])
            #option 1) include current interval + next valid interval
            #option 2) exclude current interval:  helper(j+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:
        def bs(list1, target):
            left = 0
            right = len(list1) - 1
            while left < right - 1:
                mid = (left + right) // 2
                if list1[mid][1] == target:
                    return list1[mid]
                elif list1[mid][1] < target:
                    left =  mid
                else:
                    right = mid - 1
            if list1[right][1] <= target:
                return list1[right]
            else:
                return list1[left]
        
        
        jobs = []
        for i in range(len(startTime)):
            jobs.append([startTime[i], endTime[i], profit[i]])
        dp = [[0, 0, 0]]
        
        lastMax = 0
        
        jobs.sort(key = lambda x:x[1])
        for job in jobs:
            lastMax = dp[-1][2]
            candidate = bs(dp, job[0])
            if candidate[2] + job[2] > lastMax:
                
                dp.append([job[0], job[1], candidate[2] + job[2]])
        print(dp)
        return dp[-1][-1]
        


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]
            


# topdown DP

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
            # left and right
            l = i+1
            r = len(list_jobs) - 1
            
            # keep track var
            j = len(list_jobs)
            
            while l <= r:
                middle = (l+r)//2
                
                # check the middle startTime and the i endTime
                if list_jobs[middle][0] < list_jobs[i][1]:
                    l = middle+1
                else:
                    r = middle-1
                    j = middle
            
            # find max profit
            return max(list_jobs[i][2] + find(j), find(i+1))
        
        # start at index 0
        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]: # need prev job to end bef current
                    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):
            # larger than or equal to 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
        
        # print(jobs)
                
        for i in range(1, len(jobs)):
            start, end, profit = jobs[i]
            # search for previous jobs ends before current job
            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
                
            # print(start, idx, jobs[idx][1], prev_best)
                
            dp[i] = max(dp[i - 1], profit + prev_best)
            
            # print(dp)
        
        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 - 1

#             while start <= end:
#                 mid = (start + end) // 2

#                 if intervals[index][0] < intervals[mid][1]:
#                     end = mid - 1
#                 else:
#                     start = mid + 1

#             return start - 1
        
        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])
        # print(intervals)
        # see other submitted code for clear explanation
        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)  # max of not including i, including i
            # print(intervals, i, k_th, dp)
        return max(dp)

    # almost all  test cases passed
#     def jobScheduling_n2(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:

#         def binary_search(intervals, index):

#             start = 0
#             end = index - 1

#             while start <= end:
#                 mid = (start + end) // 2

#                 if intervals[index][0] < intervals[mid][1]:
#                     end = mid - 1
#                 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])
#         # print(intervals)
#         dp = [0] * len(intervals)
#         for i in range(len(intervals)):
#             dp[i] = intervals[i][2]

#             k_th = binary_search(intervals, i)

#             if k_th != -1:
#                 for j in range(0, k_th + 1):
#                     if dp[i] < dp[j] + intervals[i][2]:
#                         dp[i] = dp[j] + intervals[i][2]

#         # print(dp)
#         return max(dp)

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

#         intervals = []
#         for i in range(len(startTime)):
#             intervals.append((startTime[i], endTime[i], profit[i]))

#         intervals.sort(key=lambda i: i[1])
#         # print(intervals)
#         dp = [0] * len(intervals)
#         for i in range(len(intervals)):
#             dp[i] = intervals[i][2]

#             for j in range(0, i):

#                 if intervals[i][0] >= intervals[j][1]:
#                     if dp[i] < dp[j] + intervals[i][2]:
#                         dp[i] = dp[j] + intervals[i][2]

#         # print(dp)
#         return max(dp)


# This class represents a job = [start-time, end-time, weight]
class Job:
    def __init__(self, start_time, end_time, weight):
        self.start_time = start_time
        self.end_time = end_time
        self.weight = weight

    #overriding hashcode and equals to use the Job object as a key in dict
    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()
        # Memoization will be done using this memory dict
        self.memory = dict()
        #computing the previous mappings
        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):
        
        # Sorting the jobs in non decreasing order of start_time - O(nlogn)
        self.jobs_start_first = sorted(self.jobs, key=lambda x: x.start_time)
        # Sorting the jobs in non decreasing order of end_time - O(nlogn)
        self.jobs_end_first = sorted(self.jobs, key=lambda x: x.end_time)
        # This list X will store the index of the previous job in jobs_end_first
        self.X[0] = -1

        # The time complexity of this method is O(n) as the statement inside the while loop
        # is only called once for each index
        # We use the intution that the latest job for the current job will be greater than or 
        # equal to the latest job for the preious job
        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

        # We now map the respective job to its index in jobs_end_first.
        # O(n)        
        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

        # Dynamic programming - checking if the subproblem is already solved
        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)

        # Storing the result in the memory
        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:
        
        # sort w.r.t. the end time
        # here the dp[i] is the max profit up to task i (the current may not be i)
        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)
            # j = search(i)
            # print(j)
            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 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.compute_latest_job_scheduled_before()
        self.memory = dict()
        

    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]

        print((self.X))
            

    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 = 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[i] stores the maximum profit if we only consider the first (i+1) jobs
        dp[0] = jobs[0][2] # Can take the first job under any circumstance
        for i in range(1, n):
            # For a new job, we can either take this new job or don't take this new job
            # Consider not taking the new job
            profit_not_take = dp[i-1]
            # Consider taking the new job
            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:
                #print(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:
        # Approach: dfs with memoization
        
        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:
        # Approach: dfs with memoization
        # after bundling start time, end time together and sort
        
        self.jobs = list()
        
        # bundle start time, end time and profit together
        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
        
        # the case when we don't do the job
        res = max(res, self.dfs(index + 1))
        
        # use binary search to find the next index if we decide to do this job
        nextIndex = self.findNext(index)
        res = max(res, self.dfs(nextIndex) + self.jobs[index][2])
        self.memo[index] = res
        
        return res
    
    # Binary search to find the next index
    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)] # up to idx, the maximum gain
        dp[0] = arr[0][2]
        for i in range(1, n):
            e, s, p = arr[i][0], arr[i][1], arr[i][2]
            # find the rightmost idx j whose end <= start
            bs, be = 0, i - 1
            ridx = -1
            while bs <= be:
                m = (bs + be) // 2
                if arr[m][0] > s:
                    be = m - 1
                else: # arr[m][1] <= s
                    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 jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        # sort intervals by their endTime
        intervals = sorted(zip(startTime, endTime, profit), key=lambda x: (x[1], x[2]))
        N = len(profit)
        # bottom up solutions: (profit, endtime, index)
        dp = [(0, 0, -1)]
        
        for idx, (s, e, p) in enumerate(intervals):
            nonoverlapping_idx = self.find_nonoverlapping_interval(dp, s + 0.1)
            # print(idx, nonoverlapping_idx, s)
            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])
        
        # print(dp)
        solutions = []
        cur_idx = dp[N][2] # of the activity
        while cur_idx != -1:
            solutions.insert(0, cur_idx)
            start_idx = intervals[cur_idx][0]
            nonoverlapping_idx = self.find_nonoverlapping_interval(dp, start_idx + 0.1)
            cur_idx = dp[nonoverlapping_idx][2]
        print(solutions)
        
        return dp[-1][0]
    
    def find_nonoverlapping_interval(self, dp, start):
        l_idx = 0
        r_idx = len(dp) - 1
        
        # print(dp, l_idx, r_idx, start)
        
        # using binary search
        while 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
        
        # print(dp, l_idx, r_idx, start)
        
        return l_idx - 1


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
            #print(left,mid,right)
            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])  
        
        #print(arr)
        
        ans = self.solve(len(profit)-1,arr)
            
        #print(self.dp)
        
        #print(self.next_index(arr,2,2))
        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)