1235. Maximum Profit in Job Scheduling #

1235. Maximum Profit in Job Scheduling

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, return the maximum profit you can take such that there are no two 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.

解題思路 #

每個工作都有兩種選擇，做或者不做。
- 做：total profit += job porfit
- 不做：nothing changed
如何選擇做不做呢？可以將工作以結束時間排序，記錄下每個結束時間的最大獲利，每次決定是否要執行當前工作時，只要找到結束時間小於等於當前開始時間的最大獲利，和上個結束時間最大獲利比較，就可以決定要不要做了。
```
dp[i] = max(dp[j]+profit, dp[i-1]) 
// j 是結束時間小於等於當前開始時間的位置
```
因為最大獲利根據結束時間是遞增的，可以用二元搜索找到。

解法：DP+Binary Search #

c++

class Solution {
public:
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        vector<vector<int>> jobs;
        for(int i = 0; i < startTime.size(); i++)
            jobs.push_back({endTime[i], startTime[i], profit[i]});
        sort(jobs.begin(), jobs.end()); // 根據結束時間排序
        map<int, int> dp = {{0, 0}};
        for(auto job: jobs) {
            // 找到小於等於開始時間的最晚結束時間，並計算獲利
            int cur = prev(dp.upper_bound(job[1]))->second + job[2]; 
            // 比較如果做了這個工作和不做的獲利
            if (cur > dp.rbegin()->second)
                dp[job[0]] = cur;
        }
        return dp.rbegin()->second;
    }
};

python

class Solution:
    def jobScheduling(self, startTime, endTime, profit):
        jobs = sorted(zip(startTime, endTime, profit), key=lambda v: v[1])
        dp = [[0, 0]]
        for s, e, p in jobs:
            i = bisect.bisect(dp, [s+1])-1
            if dp[i][1] + p > dp[-1][1]:
                dp.append([e, dp[i][1] + p])
        return dp[-1][1]