826

826. Most Profit Assigning Work (Medium)

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

Now we have some workers. worker[i] is the ability of the ith 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]

Companies:
Nutanix

Related Topics:
Two Pointers

Solution 1.

// OJ: https://leetcode.com/problems/most-profit-assigning-work/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
        map<int, int, greater<int>> diffToProfit;
        int N = difficulty.size(), maxProfit = 0, ans = 0;
        for (int i = 0; i < N; ++i) {
            diffToProfit[difficulty[i]] = max(diffToProfit[difficulty[i]], profit[i]);
        }
        for (auto it = diffToProfit.rbegin(); it != diffToProfit.rend(); ++it) {
            it->second = maxProfit = max(maxProfit, it->second);
        }
        for (int w : worker) {
            auto it = diffToProfit.lower_bound(w);
            if (it != diffToProfit.end()) ans += it->second;
        }
        return ans;
    }
};