1235. Maximum Profit in Job Scheduling

动态规划问题

本题与背包问题非常相似，本质思想还是动态规划，大致思路为：考虑将dp设为一个一维数组，其表示n时刻结束时得到的最大profits。对endTime升序排序，每当遍历到endTime时查找其对应的startTime前的最大利润（取startTime的upperbound的前一个结束时间的利润即可），加上当前利润并与dp末尾利润比较后将大者定位当前结束时刻的最大利润。代码如下：

class Solution {
public:
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        vector<vector<int>> jobs;
        for(int i=0; i<profit.size(); i++){
            jobs.push_back({endTime[i], startTime[i], profit[i]});
        }
        vector<pair<int, int>> dp(1, make_pair(0,0));
        sort(jobs.begin(), jobs.end());
        for(int i=0; i<jobs.size(); i++){
            pair<int,int> temp = {jobs[i][1], INT_MAX};
            int cur = (*(upper_bound(dp.begin(), dp.end(), temp)-1)).second+jobs[i][2];
            if(cur>dp.back().second)
                dp.push_back({jobs[i][0], cur});
        }
        return dp.back().second;
    }
};