Description

Submission

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

        sort(jobs.begin(), jobs.end());

        map<int, int> dp;

        for(auto& job: jobs) {
            int start = job[1];
            int stop = job[0];
            int p = job[2];
            
            if (dp.empty()) {
                dp[stop] = p;
                continue;
            }
            auto iter1 = dp.upper_bound(start);
            int x = prev(dp.end())->second;
            int y = (iter1 == dp.begin()) ? p : prev(iter1)->second + p;
            dp[stop] = max(y, max(x, dp[stop]));
        }

        return prev(dp.end())->second;
    }
};