#include "leetcode.h"

class Solution {
public:
  int jobScheduling(vector<int> &startTime, vector<int> &endTime,
                    vector<int> &profit) {
    int n = startTime.size();
    vvd jobs;
    for (int i = 0; i < n; ++i)
      jobs.push_back({endTime[i], startTime[i], profit[i]});
    sort(jobs.begin(), jobs.end());
    map<int, int> dp = {{0, 0}};
    for (auto &j : jobs) {
      int curr = prev(dp.upper_bound(j[1]))->second + j[2];
      if (curr > dp.rbegin()->second)
        dp[j[0]] = curr;
    }
    return dp.rbegin()->second;
  }
};

int main() {
  Solution obj;
  vector<int> startTime = {1, 2, 3, 3};
  vector<int> endTime = {3, 4, 5, 6};
  vector<int> profit = {50, 10, 40, 70};
  cout << obj.jobScheduling(startTime, endTime, profit); // 120
}