LeetCode 1235 规划兼职工作

dp+二分 我不会，记录一下

bool cmp(vector<int> a,vector<int> b){
    return a[1] < b[1];
}
class Solution {
public:
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        int n = startTime.size();
        vector<vector<int>> jobs(n);
        for(int i = 0;i<n;i++){
            jobs[i] = {startTime[i],endTime[i],profit[i]};
        }
        sort(jobs.begin(),jobs.end(),cmp);
        vector<int> dp(n+1);
        for(int i = 1;i<=n;i++){
            int k = upper_bound(jobs.begin(),jobs.begin()+i-1,jobs[i-1][0],[&](int st,const vector<int> &job)->bool{
                return st < job[1];
            }) - jobs.begin();
            dp[i] = max(dp[i-1],dp[k]+ jobs[i-1][2]);
        }
        return dp[n];
    }
};