<p>We have <code>n</code> jobs, where every job is scheduled to be done from <code>startTime[i]</code> to <code>endTime[i]</code>, obtaining a profit of <code>profit[i]</code>.</p>

<p>You&#39;re given the <code>startTime</code>, <code>endTime</code> and <code>profit</code> arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range.</p>

<p>If you choose a job that ends at time <code>X</code> you will be able to start another job that starts at time <code>X</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2019/10/10/sample1_1584.png" style="width: 380px; height: 154px;" /></strong></p>

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

<p><strong class="example">Example 2:</strong></p>

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2019/10/10/sample22_1584.png" style="width: 600px; height: 112px;" /> </strong></p>

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

<p><strong class="example">Example 3:</strong></p>

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2019/10/10/sample3_1584.png" style="width: 400px; height: 112px;" /></strong></p>

<pre>
<strong>Input:</strong> startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
<strong>Output:</strong> 6
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= startTime.length == endTime.length == profit.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= startTime[i] &lt; endTime[i] &lt;= 10<sup>9</sup></code></li>
	<li><code>1 &lt;= profit[i] &lt;= 10<sup>4</sup></code></li>
</ul>

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

        # endTimeSet = set(endTime)
        # startTimeSet = set(startTime)
        # total = endTimeSet | startTimeSet 
        # total = list(total)
        # dic = defaultdict(list)
        # total = sorted(total)
        # for i in range(len(endTime)):
        #     dic[endTime[i]].append((i, startTime[i]))
        
        
        # dp = [0] * len(total) 
        # dic_time_index = {}
        # # 找到time对应的index因为为了给dic取
        # for i in range(len(total)):
        #     dic_time_index[total[i]] = i

        # for i in range(len(dp)):
        #     if total[i] in endTimeSet:
        #         res = 0 
        #         for index, start in dic[total[i]]:
        #             res = max(res, dp[dic_time_index[start]]+ profit[index])
        #         dp[i] = max(res, dp[i-1])
        #     else:
        #         dp[i] = max(dp[i], dp[i-1] if i > 0 else 0)
        # # print(dp)
        # return max(dp)

        # endTimeSet = set(endTime)
        # startTimeSet = set(startTime)
        # total = endTimeSet | startTimeSet 

        # minTime = min(total)
        # maxTime = max(total)
        # dp = {i:0 for i in range(minTime, maxTime+1)}
        # dic = defaultdict(list)
        # for i in range(len(startTime)):
        #     dic[endTime[i]].append(startTime[i])
        
        # profit_dic = {}
        # for index, end in enumerate(endTime):
        #     profit_dic[end] = profit[index]

        
        # for i in range(minTime, maxTime+1):
        #     if i in endTime:
        #         for start in dic[i]:
        #             dp[i] = max(dp[i], dp[start] + profit_dic[i])
        #     else:
        #         dp[i] = dp[i-1] if i>minTime else 0
        
        # # print(dp)
        # res = 0
        # for i in dp:
        #     res = max(res, dp[i])
        # return res
        memo = {}
        def findNextPosition(curend):
            start = 0 
            end = len(startTime)-1
            next_index = len(startTime)
            while start <= end:
                mid = start+ (end-start)//2
                if startTime[mid] >= curend:
                    next_index = mid 
                    end = mid-1 
                else:
                    start = mid+1 
            
            return next_index

        timeSet = []
        for i in range(len(startTime)):
            timeSet.append((startTime[i], endTime[i], profit[i]))
        
        timeSet = sorted(timeSet, key = lambda x: x[0])
        startTime.sort()
        def dfs(position):
            if position == len(startTime):
                return 0 
            
            if position in memo:
                return memo[position]
            
            next_index = findNextPosition(timeSet[position][1])

            skip_profit = dfs(position+1)
            next_profit = dfs(next_index) + timeSet[position][2]

            maxProfit = max(skip_profit, next_profit)

            memo[position] = maxProfit
            return maxProfit

        return dfs(0)



58639