lc1235

class Solution
{
  public:
    int jobScheduling(vector<int> &startTime, vector<int> &endTime, vector<int> &profit)
    {
        vector<int> vt;
        for (auto t : startTime)
            vt.push_back(t);
        for (auto t : endTime)
            vt.push_back(t);
        sort(vt.begin(), vt.end());
        vt.erase(unique(vt.begin(), vt.end()), vt.end());

        // vector<int> dp(vt.back() + 1);
        vector<int> dp(vt.size() + 1);

        vector<vector<int>> times;
        for (int i = 0; i < startTime.size(); ++i) {
            int s = lower_bound(vt.begin(), vt.end(), startTime[i]) - vt.begin() + 1;
            int e = lower_bound(vt.begin(), vt.end(), endTime[i]) - vt.begin() + 1;
            times.push_back({e, s, profit[i]});
        }
        sort(times.begin(), times.end());

        for (int i = 1, j = 0; i < dp.size(); ++i) {
            dp[i] = dp[i - 1];
            while (j < times.size() && i >= times[j][0]) {
                dp[i] = max(dp[i], dp[times[j][1]] + times[j][2]);
                ++j;
            }
        }
        return dp.back();
    }
};