1235

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

        // Sort jobs on end time.
        sort(jobs.begin(), jobs.end());

        // Have a dp array where last entry is most profitable.
        map<int, int> dp = {{0,0}};
        for(auto job:jobs){
            int sTime = job[1], eTime = job[0];
            auto pos = --dp.upper_bound(sTime);
            if(pos->second+job[2] > dp.rbegin()->second)
            dp[eTime] = pos->second+job[2];
        }
        return dp.rbegin()->second;
    }
};