Leet Code Daily 2024-06-18 - Most Profit Assigning Work
Solution
- Given each worker is independent, we can see this as RMQ problem and each worker represents one query.
- Or we can just sort.
Code
● ● ●c++class Solution {
public:
int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit,
vector<int>& worker) {
int n = difficulty.size();
vector<pair<int, int>> jobs;
for (int i = 0; i < n; i++) {
jobs.push_back(make_pair(difficulty[i], profit[i]));
}
sort(jobs.begin(), jobs.end(),
[](const auto& x, const auto& y) { return x.first < y.first; });
for (int i = 1; i < n; i++) {
jobs[i].second = max(jobs[i].second, jobs[i - 1].second);
}
sort(worker.begin(), worker.end());
int i = 0, ans = 0;
for (const auto& w : worker) {
while (i + 1 < n && jobs[i + 1].first <= w) {
i++;
}
if (jobs[i].first <= w) {
ans += jobs[i].second;
}
}
return ans;
}
};