leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1235.cpp (745B)

      1 class Solution {
      2   public:
      3     int jobScheduling(const vector<int> &startTime, const vector<int> &endTime,
      4                       const vector<int> &profit) const {
      5         static int indices[50001];
      6         const int n = profit.size();
      7 
      8         iota(begin(indices), begin(indices) + n, 0);
      9         sort(begin(indices), begin(indices) + n,
     10              [&endTime](int a, int b) { return endTime[a] < endTime[b]; });
     11 
     12         map<int, int> dp = {{0, 0}};
     13         for (int i = 0; i < n; i++) {
     14             const int idx = indices[i];
     15             const int crnt = profit[idx] + prev(dp.upper_bound(startTime[idx]))->second;
     16             if (crnt > dp.rbegin()->second) dp[endTime[idx]] = crnt;
     17         }
     18 
     19         return dp.rbegin()->second;
     20     }
     21 };