1235. Maximum Profit in Job Scheduling

這題我覺得算是很經典的DP題, 首先我們根據結束時間先做排序

然後我們令dp[time] = profit當作當前時間的最大收益

然後我們可以倆倆任務做確認, 假設沒重疊, 然後當前的任務加上先前的任務可以為最大值的話, 我們就更新dp

詳情可以看https://www.youtube.com/watch?v=cr6Ip0J9izc&ab_channel=TusharRoy-CodingMadeSimple 這個教學

class Solution {
public:
    static bool sortEndTime(vector<int> &a, vector<int> &b){
        if(a[1] == b[1]) return a[0] < b[0];
        return a[1] < b[1];
    }
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        vector<vector<int>> m(startTime.size());
        for(int i = 0 ; i < startTime.size();i++){
            m[i] = {startTime[i], endTime[i], profit[i]};
        }
        sort(m.begin(), m.end(), sortEndTime);
        vector<int> dp(m.size());
        int res = 0;
        for(int i = 0;i < dp.size();i++) dp[i] = m[i][2];
        
        for(int i = 0 ; i < m.size();i++){
            for(int j = 0; j < i;j++){
                if(m[j][1] <= m[i][0]) 
                    dp[i] = max(dp[i], dp[j] + m[i][2]);
             
                res = max(res, dp[i]);
            }
        }
        return res;
    }
};

但這個時間複雜度是O(n²), 會TLE, 提式有說明可以用binary search, 要怎麼做呢？

要把上面的想法給換掉

好難喔

我們從小做到大, 我們直接抓取不與當前index重疊的最後一個jobs, 如果存在, 我們就使用他的dp, 因為我們預想他的dp已經是對他來說最好的值. 如果這樣的jobs不存在呢？ 沒關係我們直接就是當前jobs的profit 直接跟前一個dp比較就行了, 看是不是我什麼組合都不做就已經比你做了一堆組合還要好

class Solution {
public:
    static bool sortEndTime(vector<int> &a, vector<int> &b){
        if(a[1] == b[1]) return a[0] < b[0];
        return a[1] < b[1];
    }
    int bs_index(vector<vector<int>> &jobs, int index){
        int l = 0;
        int r = index - 1;
        while(l <= r){
            int mid = (l + r) /2;
            if(jobs[mid][1] <= jobs[index][0]){
                if(jobs[mid + 1][1] <= jobs[index][0]){
                    l = mid + 1;
                }else{
                    return mid;
                }
            }else{
                r = mid - 1;
            }
        }
        return -1;
    }
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        vector<vector<int>> m(startTime.size());
        for(int i = 0 ; i < startTime.size();i++){
            m[i] = {startTime[i], endTime[i], profit[i]};
        }
        sort(m.begin(), m.end(), sortEndTime);
        vector<int> dp(m.size());
        int res = 0;
        dp[0] = m[0][2];
        for(int i = 1 ; i < m.size();i++){
            int cur_profit = m[i][2];
            int l = bs_index(m, i);   
            if(l != -1){
                cur_profit += dp[l];
            }
            dp[i] = max(cur_profit, dp[i - 1]);
}
        return dp[m.size() - 1];
    }
};

由於在找那個最大值我們用了binary search, 所以我們可以用O(nlogn)的時間複雜度完成