Maximum Profit in Job Scheduling

'''
- First of all, sort the jobs by start time.
- For every job, we have only two options:
    1) Take the current job
    2) Do not take the current job

- If we take the current job, then we cannot take any job that starts before the current job ends.
  So instead of checking every future job, we directly jump to the next valid job.

- To find the next valid job:
    - Create a sorted list of startTime from the sorted jobs.
    - Use bisect_left on this startTime list with the current job's end time.
    - This gives the index of the first job whose start time is >= current job's end time.

- Transition:
    not_take = fun(i+1)
    take = profit[i] + fun(next_idx)
    dp[i] = max(take, not_take)

Trick:
- First capsule (startTime, endTime, profit) into one list `jobs` and sort it.
- Then extract startTime from the sorted jobs into a separate array for bisect_left.
'''

from bisect import bisect_left
def fun(i,dp,jobs,startTime):
    if i==len(jobs):
        return 0

    if dp[i]!=-1:
        return dp[i]

    not_take_it=fun(i+1,dp,jobs,startTime)

    next_idx=bisect_left(startTime, jobs[i][1])
    take_it=jobs[i][2]+fun(next_idx,dp,jobs,startTime)
    dp[i]=max(not_take_it,take_it)
    return dp[i]

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.sort()
        startTime = [job[0] for job in jobs]

        n=len(startTime)
        dp=[-1 for  i in range(len(startTime))]
        fun(0,dp,jobs,startTime)
        return max(dp)