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
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)
        

        
            
            
            

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)
        

        
            
            
            
