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

        # first using memorized recursion
        # sort by the end_time - if I choose to get the last done, then based on the starting time, I could choose to do other jobs, thus it is a smaller size question

        # now consider how to write the code
        # f[i] = f[i-1]
        # f[i] = f[j] + profit[i] and endTime[j] <= startTime[i]
        # define f[i] to be the maximum profit that you could get in first i jobs, based on the timestamp of the ending time
        # f[i] = max(f[i-1], f[j]+profit[i])
        # f[i+1] = max(f[i], f[j+1]+profit[i])
        # f[0] = 0

        # jobs = sorted(zip(endTime, startTime, profit))
        # # initialization
        # dp = [0] * (len(jobs) + 1)

        # # 反向的写法

        # # 同样的代码 为什么过不去？？？？？自从用了bisect -> 因为要用bisect_right, 而不是bisect_left
        # # 定义作业结构
        # jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])

        # end_times = [x[1] for x in jobs]
        
        # # 初始化备忘录
        # # memo = [0] * len(jobs)
        # @cache
        # def dfs(i: int) -> int:

        #     if i < 0:
        #         return 0
        #     # if memo[i] != 0:
        #     #     return memo[i]
            
        #     # 使用二分查找来找到下一个可以安排的作业
        #     # l, r = 0, i
        #     # while l < r:
        #     #     mid = (l + r) // 2
        #     #     if jobs[mid][1] > jobs[i][0]:
        #     #         r = mid
        #     #     else:
        #     #         l = mid + 1

        #     # try to use the in-built function
        #     # l = bisect_right(end_times, jobs[i][0])
        #     l = bisect_left(end_times, jobs[i][0]+1)

        #     # Review the definition of the binary search - when searching for the lower bound left-1 < target, right>=target
            
        #     j = l - 1 # j 是选了 jobs[i] 的下一个能选的工作时间
        #     # if jobs[i][0] < jobs[j][1]:
        #     #     j = -1
            
        #     # 选择不安排当前作业或者安排当前作业
        #     res = max(dfs(i - 1), (dfs(j) + jobs[i][2]))
        #     # memo[i] = res
        #     return res
        
        # return dfs(len(jobs) - 1)

        # # 正向的写法

        # # 将工作按结束时间排序
        # jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])
        
        # # 提取排序后的开始时间、结束时间和利润
        # starts, ends, profits = zip(*jobs)
        
        # # 记忆化存储
        # memo = {}
        
        # @cache
        # def dfs(index: int) -> int:

        #     if index >= len(jobs):
        #         return 0
            
        #     # if index in memo:
        #     #     return memo[index]
            
        #     # 当前工作
        #     current_start, current_end, current_profit = jobs[index]
            
        #     # 找到下一个可以选择的工作
        #     next_index = bisect.bisect_left(starts, current_end)
            
        #     # 选择当前工作
        #     take_current = current_profit + dfs(next_index)
        #     # 不选择当前工作
        #     skip_current = dfs(index + 1)
            
        #     # 存储结果并返回最大值
        #     # memo[index] = max(take_current, skip_current)
        #     return max(take_current, skip_current)
        
        # return dfs(0)

        # # 将工作按结束时间排序
        # jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])
        
        # # 提取排序后的开始时间、结束时间和利润
        # starts = [job[0] for job in jobs]
        # ends = [job[1] for job in jobs]
        # profits = [job[2] for job in jobs]
        
        # # 记忆化存储
        # @lru_cache(None)
        # def dfs(index: int) -> int:
        #     if index >= len(jobs):
        #         return 0
            
        #     # 当前工作
        #     current_start, current_end, current_profit = jobs[index]
            
        #     # 找到下一个可以选择的工作
        #     next_index = bisect.bisect_left(starts, current_end)
            
        #     # 选择当前工作
        #     take_current = current_profit + dfs(next_index)
        #     # 不选择当前工作
        #     skip_current = dfs(index + 1)
            
        #     # 存储结果并返回最大值
        #     return max(take_current, skip_current)
        
        # return dfs(0)

        n = len(profit)
        jobs = sorted(zip(startTime, endTime, profit))
        start_times = [x[0] for x in jobs]

        def find(i: int) -> int:
            left, right = i + 1, n - 1
            while left <= right:
                mid = left + right >> 1
                if jobs[i][1] <= jobs[mid][0]:
                    right = mid - 1
                else:
                    left = mid + 1
            return left
        
        @cache
        def dfs(i: int) -> int:
            if i >= n:
                return 0
            next_index = bisect_left(start_times, jobs[i][1])
            return max(dfs(find(i)) + jobs[i][2], dfs(i + 1))
        
        return dfs(0)

912