leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1235.cpp (745B)

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