diff options
Diffstat (limited to 'other/max_profit_job.cpp')
-rw-r--r-- | other/max_profit_job.cpp | 28 |
1 files changed, 28 insertions, 0 deletions
diff --git a/other/max_profit_job.cpp b/other/max_profit_job.cpp new file mode 100644 index 0000000..811874b --- /dev/null +++ b/other/max_profit_job.cpp @@ -0,0 +1,28 @@ +#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 +} |