Formatted question description: https://leetcode.ca/all/826.html

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/
// 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;
    }
};

Java

class Solution {
    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        int jobs = difficulty.length;
        int[][] difficultyProfit = new int[jobs][2];
        for (int i = 0; i < jobs; i++) {
            difficultyProfit[i][0] = difficulty[i];
            difficultyProfit[i][1] = profit[i];
        }
        Arrays.sort(difficultyProfit, new Comparator<int[]>() {
            public int compare(int[] difficultyProfit1, int[] difficultyProfit2) {
                if (difficultyProfit1[0] != difficultyProfit2[0])
                    return difficultyProfit1[0] - difficultyProfit2[0];
                else
                    return difficultyProfit2[1] - difficultyProfit1[1];
            }
        });
        for (int i = 1; i < jobs; i++)
            difficultyProfit[i][1] = Math.max(difficultyProfit[i - 1][1], difficultyProfit[i][1]);
        int totalProfit = 0;
        for (int ability : worker) {
            int maxProfit = binarySearch(difficultyProfit, ability);
            totalProfit += maxProfit;
        }
        return totalProfit;
    }

    public int binarySearch(int[][] difficultyProfit, int ability) {
        int low = 0, high = difficultyProfit.length - 1;
        int index = -1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            int difficulty = difficultyProfit[mid][0];
            if (difficulty == ability) {
                index = mid;
                break;
            } else if (difficulty > ability)
                high = mid - 1;
            else
                low = mid + 1;
        }
        if (index < 0)
            index = low - 1;
        if (index < 0)
            return 0;
        else
            return difficultyProfit[index][1];
    }
}

// OJ: https://leetcode.com/problems/most-profit-assigning-work/
// 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;
    }
};

class Solution(object):
    def maxProfitAssignment(self, difficulty, profit, worker):
        """
        :type difficulty: List[int]
        :type profit: List[int]
        :type worker: List[int]
        :rtype: int
        """
        jobs = sorted([a, b] for a, b in zip(difficulty, profit))
        curMax, i = 0, 0
        res = 0
        for w in sorted(worker):
            while i < len(jobs) and w >= jobs[i][0]:
                curMax = max(curMax, jobs[i][1])
                i += 1
            res += curMax
        return res

826 - Most Profit Assigning Work

826. Most Profit Assigning Work (Medium)

Solution 1.

All Problems

All Solutions