# 826. Most Profit Assigning Work

We have jobs: `difficulty[i]` is the difficulty of the `i`th job, and `profit[i]` is the profit of the `i`th job.

Now we have some workers. `worker[i]` is the ability of the `i`th worker, which means that this worker can only complete a job with difficulty at most `worker[i]`

Every worker can be assigned at most one job, but one job can be completed multiple times.

For example, if 3 people attempt the same job that pays \$1, then the total profit will be \$3.  If a worker cannot complete any job, his profit is \$0.

What is the most profit we can make?

Example 1:

``````Input: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
Output: 100
Explanation: Workers are assigned jobs of difficulty [4,4,6,6] and they get profit of [20,20,30,30] seperately.
``````

Notes:

• `1 <= difficulty.length = profit.length <= 10000`
• `1 <= worker.length <= 10000`
• `difficulty[i], profit[i], worker[i]`  are in range `[1, 10^5]`

``````class Solution {
public:
int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
int res = 0, cur = 0;
map<int, int> m;
for (int i = 0; i < difficulty.size(); ++i) {
m[difficulty[i]] = max(m[difficulty[i]], profit[i]);
}
for (auto &a : m) {
a.second = max(a.second, cur);
cur = a.second;
}
for (int i = 0; i < worker.size(); ++i) {
auto it = m.upper_bound(worker[i]);
if (it != m.begin()) {
res += (--it)->second;
}
}
return res;
}
};
``````

``````class Solution {
public:
int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
int res = 0, n = profit.size(), curMax = 0, i = 0;
vector<pair<int, int>> jobs;
for (int j = 0; j < n; ++j) {
jobs.push_back({difficulty[j], profit[j]});
}
sort(jobs.begin(), jobs.end());
sort(worker.begin(), worker.end());
for (int ability : worker) {
while (i < n && ability >= jobs[i].first) {
curMax = max(curMax, jobs[i++].second);
}
res += curMax;
}
return res;
}
};
``````

``````class Solution {
public:
int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
int res = 0, n = profit.size();
vector<int> dp(100001);
for (int i = 0; i < n; ++i) {
dp[difficulty[i]] = max(dp[difficulty[i]], profit[i]);
}
for (int i = 1; i < dp.size(); ++i) {
dp[i] = max(dp[i], dp[i - 1]);
}
for (int ability : worker) {
res += dp[ability];
}
return res;
}
};
``````

https://leetcode.com/problems/most-profit-assigning-work/

https://leetcode.com/problems/most-profit-assigning-work/discuss/127133/Java-Solution-with-TreeMap

https://leetcode.com/problems/most-profit-assigning-work/discuss/127031/C%2B%2BJavaPython-Sort-and-Two-pointer

https://leetcode.com/problems/most-profit-assigning-work/discuss/126988/O(M-%2B-N)-solution-based-on-preprocessing

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation