aboutsummaryrefslogtreecommitdiff
path: root/other/max_profit_job.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/max_profit_job.cpp')
-rw-r--r--other/max_profit_job.cpp28
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
+}