Leetcode 1235. 规划兼职工作（DAY 73） ---- 动态规划学习期（上午去上高数课了 课下老师说上次旷课不扣平时分嘻嘻）

原题题目

代码实现（首刷TLE 24/27)

class Solution {
    
public:int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
    int size = startTime.size(),ret = -1;vector<vector<int>> temp;for(int i=0;i<size;++i)temp.push_back({
    startTime[i],endTime[i],profit[i]});vector<int> dp(size+1,0);sort(temp.begin(),temp.end(),[](const vector<int>& a,const vector<int>& b){
     return a[1]<b[1];});for(int i=0;i<size;i++){
    dp[i] = profit[i];for(int j=0;j<i;j++){
    if(endTime[j] <= startTime[i])dp[i] = max(dp[i],dp[j]+profit[i]);else    break;}ret = max(dp[i],ret);}return ret;}
};

代码实现（二分加速给我绕晕了 cv别人的二分加速代码）

class Solution {
    
public:int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
    int n = startTime.size();vector<int> id(n);iota(id.begin(), id.end(), 0);// 生成序列 0,1，2，。。。sort(id.begin(), id.end(),[&](auto a, auto b){
    return endTime[a] < endTime[b];//按结束时间排序});map<int,int> dp;dp[0] = 0;//边界dp[endTime[id[0]]] = profit[id[0]];//第一个状态int ans = profit[id[0]];for(int i = 1; i < n; i++){
    int idx = id[i];//序号auto it = dp.upper_bound(startTime[idx]);//二分查找int dp_prev = (--it)->second;//上一个不冲突结束时间点的最大收益dp[endTime[idx]] = max(ans, max(dp[endTime[idx]], dp_prev+profit[idx]));ans = max(ans, dp[endTime[idx]]);}return ans;}
};