Most Profit Assigning Work — Medium Problem & Solution

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

Difficulty: Medium
Topics: Arrays, Greedy, Sorting, Two Pointers
Asked at: Amazon, Google, Zoho
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

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

Pair each difficulty with its profit and sort the pairs by difficulty.
Sort the workers ascending.
For each worker, advance the job pointer over every job they can do, keeping best, the maximum profit seen so far.
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

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue