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

# 2024/09/15
# 面试前刷Doordash高频题
#
# 最直接办法是DFS
# 共n层，每层表示第i个job是否take
# 通过判断是否overlap来剪枝
# O(2^n)
# DP似乎可以，比如M[i]表示以第i个job为结束的最大profit
# 左大段 + 右小段
# M[i] = profit[i] + max(M[j]) where end[j] <= start[i]
# M[0] = profit[0]
# return max(M)
# Time: O(n^2)
# 有一个可以优化，看M[j]的时候，如果where成立，记录其对应的max start，之后遇到新的M[j]，如果对应的end小于max start的话，就不用看了
# 但还是要每个遍历变，毕竟是按照start sort的
# 写完后发现是按照end sort的，所以优化思路还是对的
class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        n = len(startTime)
        jobs = [(endTime[i], startTime[i], profit[i]) for i in range(n)]

        # 需要按照end sort
        jobs.sort()

        M = [0] * n

        for i in range(n):
            local_max = 0
            for j in range(i):
                if jobs[j][0] <= jobs[i][1]:
                    local_max = max(local_max, M[j])
            M[i] = jobs[i][2] + local_max

        return max(M)
# 超时了
# 之前优化的思路应该对的，重新改一下
class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        n = len(startTime)
        jobs = [(endTime[i], startTime[i], profit[i]) for i in range(n)]

        # 需要按照end sort
        jobs.sort()

        M = [0] * n

        for i in range(n):
            local_max = 0
            max_start = -1
            for j in range(i - 1, -1, -1):
                if jobs[j][0] <= max_start:
                    break
                if jobs[j][0] <= jobs[i][1]:
                    local_max = max(local_max, M[j])
                    max_start = max(max_start, jobs[j][1])
            M[i] = jobs[i][2] + local_max

        return max(M)
# 还是超时了，但比之前过了更多的testcases，毕竟还是O(n^2)
# 说明有O(nlogn)或者O(n)的方法
# 没什么思路，看答案去了
# 确实可以binary search，原则是找到第一个end <= cur_start
# 不对，我的M定义不能用binary search，需要改为前i个job的最大profit，可以不包括i
# https://leetcode.com/problems/maximum-profit-in-job-scheduling/solutions/409009/java-c-python-dp-solution
# If we don't do this job, nothing will be changed.
# If we do this job, binary search in the dp to find the largest profit we can make before start time s.
# So we also know the maximum cuurent profit that we can make doing this job.
# Compare with last element in the dp,
# we make more money,
# it worth doing this job,
# then we add the pair of [e, cur] to the back of dp.
# Otherwise, we'd like not to do this job.
# Intial dp[0] = 0, as we make profit = 0 at time = 0.
# 照着这个写一下
# class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        jobs = sorted(zip(endTime, startTime, profit))

        M = [[0, 0]]
        for end, start, p in jobs:
            # index = bisect.bisect(M, [start + 1, 0]) - 1
            index = bisect.bisect(M, [start, float("inf")]) - 1
            if M[index][1] + p > M[-1][1]:
                M.append([end, M[index][1] + p])

        return M[-1][1]
625