Most Profit Assigning Work

Medium
768.

Most Profit Assigning Work

Most Profit Assigning Work is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and Zoho interviews.

Job i has difficulty difficulty[i] and pays profit[i]. Worker j can take any job whose difficulty is at most worker[j].

Each worker takes at most one job, but a job may be taken by any number of workers (or none). Return the maximum total profit.

Example 1

Input
difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
Output
100
Explanation
The workers earn 20, 20, 30 and 30.

Example 2

Input
difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25]
Output
0
Explanation
No worker is strong enough for any job.

Example 3

Input
difficulty = [1,1,1], profit = [5,3,9], worker = [2]
Output
9
Explanation
The worker picks the best of the three equally easy jobs.

Constraints

  • 1 <= difficulty.length == profit.length <= 10000
  • 1 <= worker.length <= 10000
  • 1 <= difficulty[i], profit[i], worker[j] <= 100000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} difficulty
 * @param {number[]} profit
 * @param {number[]} worker
 * @return {number}
 */
var maxProfitAssignment = function(difficulty, profit, worker) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Most Profit Assigning Work — Solution in Python, Java & C++

Most Profit Assigning Work solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Most Profit Assigning Work is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and Zoho interviews.

Problem statement

Job i has difficulty difficulty[i] and pays profit[i]. Worker j can take any job whose difficulty is at most worker[j].

Each worker takes at most one job, but a job may be taken by any number of workers (or none). Return the maximum total profit.

Example 1

Input: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
Output: 100
Explanation: The workers earn 20, 20, 30 and 30.

Example 2

Input: difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25]
Output: 0
Explanation: No worker is strong enough for any job.

Example 3

Input: difficulty = [1,1,1], profit = [5,3,9], worker = [2]
Output: 9
Explanation: The worker picks the best of the three equally easy jobs.

Constraints

  • 1 <= difficulty.length == profit.length <= 10000
  • 1 <= worker.length <= 10000
  • 1 <= difficulty[i], profit[i], worker[j] <= 100000

Hints for Most Profit Assigning Work

  1. Hint 1

    Each worker independently wants the highest-paying job they can do — there is no competition for jobs.

  2. Hint 2

    Sort the jobs by difficulty and the workers by strength, then sweep both together.

  3. Hint 3

    Keep a running maximum of the profit among jobs already admitted; a stronger worker can only do more.

How to solve Most Profit Assigning Work

Because a job can be taken any number of times, each worker's choice is independent: take the most profitable job within reach. Sorting both lists lets a single pointer accumulate the best profit reachable as the workers get stronger.

Approach

  1. Pair each difficulty with its profit and sort the pairs by difficulty.
  2. Sort the workers ascending.
  3. For each worker, advance the job pointer over every job they can do, keeping best, the maximum profit seen so far.
  4. Add best to the total.

Why it works

best is the maximum profit over all jobs of difficulty at most the current worker's strength, which is exactly what that worker can earn. Sorting the workers makes the set of reachable jobs grow monotonically, so the pointer never moves backwards and each job is admitted once.

Complexity

  • Time — O(n log n + m log m)
  • Space — O(n)

Pitfalls

  • A harder job is not necessarily better paid, so the maximum has to be carried forward rather than read off the last admitted job.
  • Trying to assign each job to at most one worker is a different (matching) problem.
  • The total reaches about 10^4 · 10^5 = 10^9, which still fits int — but only just.

Reference solution

Python

from typing import List

def maxProfitAssignment(difficulty: List[int], profit: List[int], worker: List[int]) -> int:
    jobs = sorted(zip(difficulty, profit))
    total = 0
    j = 0
    best = 0
    for cap in sorted(worker):
        while j < len(jobs) and jobs[j][0] <= cap:
            best = max(best, jobs[j][1])
            j += 1
        total += best
    return total

Java

public static int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
    int n = difficulty.length;
    int[][] jobs = new int[n][2];
    for (int i = 0; i < n; i++) {
        jobs[i][0] = difficulty[i];
        jobs[i][1] = profit[i];
    }
    Arrays.sort(jobs, (a, b) -> Integer.compare(a[0], b[0]));
    int[] w = worker.clone();
    Arrays.sort(w);
    int total = 0, j = 0, best = 0;
    for (int cap : w) {
        while (j < n && jobs[j][0] <= cap) {
            best = Math.max(best, jobs[j][1]);
            j++;
        }
        total += best;
    }
    return total;
}

C++

int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
    int n = (int) difficulty.size();
    vector<pair<int, int>> jobs(n);
    for (int i = 0; i < n; i++) jobs[i] = make_pair(difficulty[i], profit[i]);
    sort(jobs.begin(), jobs.end());
    vector<int> w = worker;
    sort(w.begin(), w.end());
    int total = 0, j = 0, best = 0;
    for (int cap : w) {
        while (j < n && jobs[j].first <= cap) {
            best = max(best, jobs[j].second);
            j++;
        }
        total += best;
    }
    return total;
}

JavaScript

var maxProfitAssignment = function(difficulty, profit, worker) {
    var jobs = [];
    for (var i = 0; i < difficulty.length; i++) jobs.push([difficulty[i], profit[i]]);
    jobs.sort(function(a, b) { return a[0] - b[0]; });
    var w = worker.slice().sort(function(a, b) { return a - b; });
    var total = 0, j = 0, best = 0;
    for (var k = 0; k < w.length; k++) {
        while (j < jobs.length && jobs[j][0] <= w[k]) {
            if (jobs[j][1] > best) best = jobs[j][1];
            j++;
        }
        total += best;
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms