Description

Submission

class Solution {
public:
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        vector<vector<int>> jobs;
        int n = startTime.size();
        for(int i = 0; i < n; ++i) {
            jobs.push_back({startTime[i], endTime[i], profit[i]});
        }

        sort(jobs.begin(), jobs.end(), [](auto& v1, auto& v2) {
            return v1[1] < v2[1];
        });

        map<int, int> dp;

        int ret = 0;
        for(int i = 0; i < n; ++i) {
            auto iter = dp.upper_bound(jobs[i][0]);
            int cur = ret;
            if(iter == dp.begin()) {
                cur = max(cur, jobs[i][2]);
            } else {
                cur = max(cur, prev(iter)->second + jobs[i][2]);
            }

            dp[jobs[i][1]] = cur;
            ret = max(cur, ret);
        }

        return ret;
    }
};