1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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
}
|