LeetCode 826: Most Profit Assigning Work

Problem Restatement

We are given three arrays:

Each worker can do at most one job.

A job can be used more than once. This is important. If three workers all choose the same job, we count that job’s profit three times.

If a worker cannot do any job, that worker contributes 0.

The task is to return the maximum total profit.

Input and Output

Function shape:

class Solution:
    def maxProfitAssignment(
        self,
        difficulty: list[int],
        profit: list[int],
        worker: list[int],
    ) -> int:
        ...

Examples

Example 1:

difficulty = [2, 4, 6, 8, 10]
profit = [10, 20, 30, 40, 50]
worker = [4, 5, 6, 7]

Worker ability 4 can do jobs with difficulty 2 and 4.

The best profit is 20.

Worker ability 5 can also do jobs with difficulty 2 and 4.

The best profit is 20.

Worker ability 6 can do jobs with difficulty 2, 4, and 6.

The best profit is 30.

Worker ability 7 can do jobs with difficulty 2, 4, and 6.

The best profit is 30.

Total:

20 + 20 + 30 + 30 = 100

So the answer is:

100

Example 2:

difficulty = [85, 47, 57]
profit = [24, 66, 99]
worker = [40, 25, 25]

Every job has difficulty greater than every worker’s ability.

No worker can do any job.

So the answer is:

0

First Thought: Brute Force

For each worker, check every job.

If the worker can do the job, keep the best profit seen so far.

class Solution:
    def maxProfitAssignment(
        self,
        difficulty: list[int],
        profit: list[int],
        worker: list[int],
    ) -> int:
        total = 0

        for ability in worker:
            best = 0

            for d, p in zip(difficulty, profit):
                if d <= ability:
                    best = max(best, p)

            total += best

        return total

This gives the correct answer.

For every worker, it finds the most profitable job that worker can complete.

Problem With Brute Force

Let:

n = len(difficulty)
m = len(worker)

The brute force solution checks every job for every worker.

The time complexity is:

O(n * m)

The constraints allow up to 10^4 jobs and 10^4 workers.

That can mean:

10^4 * 10^4 = 10^8

checks, which is too much for a clean solution.

We need to avoid restarting the job scan for every worker.

Key Insight

Sort jobs by difficulty.

Sort workers by ability.

Then process workers from weakest to strongest.

When we reach a worker with ability ability, all jobs with difficulty less than or equal to ability are available to that worker.

Because workers are sorted, the next worker has equal or greater ability. So any job available to the current worker will also be available to the next worker.

This means we can scan the jobs only once.

While scanning, keep the best profit among all jobs seen so far.

Algorithm

First, combine each job’s difficulty and profit:

jobs = sorted(zip(difficulty, profit))

Then sort workers:

worker.sort()

Use two variables:

For each worker ability:

1. Add all jobs whose difficulty is at most ability.
2. Update best with the maximum profit among those jobs.
3. Add best to the total answer.

Because the same job can be reused, we do not remove a job after assigning it.

That is why this greedy scan works.

Walkthrough

Use:

difficulty = [2, 4, 6, 8, 10]
profit = [10, 20, 30, 40, 50]
worker = [4, 5, 6, 7]

After sorting jobs:

jobs = [(2, 10), (4, 20), (6, 30), (8, 40), (10, 50)]

Workers are already sorted:

worker = [4, 5, 6, 7]

Now scan.

For worker 4, available jobs are:

(2, 10), (4, 20)

Best profit is 20.

Total is now 20.

For worker 5, no new jobs become available. Best profit stays 20.

Total is now 40.

For worker 6, job (6, 30) becomes available. Best profit becomes 30.

Total is now 70.

For worker 7, no new jobs become available. Best profit stays 30.

Total is now 100.

Return:

100

Correctness

We process workers in nondecreasing order of ability.

For any current worker, all jobs with difficulty less than or equal to that worker’s ability are feasible.

The pointer j advances through the sorted jobs and includes exactly those feasible jobs. Since jobs are sorted by difficulty, once a job has difficulty greater than the current worker’s ability, no later job can be feasible for that worker.

The variable best stores the maximum profit among all jobs already included.

Therefore, for each worker, best is exactly the largest profit among all jobs that worker can complete.

Adding best for each worker is valid because each worker can do at most one job, and the same job may be completed multiple times by different workers.

So the algorithm adds the best possible profit for every worker, which gives the maximum total profit.

Complexity

The scan itself is linear:

O(n + m)

So sorting dominates the runtime.

Implementation

class Solution:
    def maxProfitAssignment(
        self,
        difficulty: list[int],
        profit: list[int],
        worker: list[int],
    ) -> int:
        jobs = sorted(zip(difficulty, profit))
        worker.sort()

        total = 0
        best = 0
        j = 0

        for ability in worker:
            while j < len(jobs) and jobs[j][0] <= ability:
                best = max(best, jobs[j][1])
                j += 1

            total += best

        return total

Code Explanation

We first pair each job difficulty with its profit:

jobs = sorted(zip(difficulty, profit))

This creates pairs like:

(difficulty, profit)

and sorts them by difficulty.

Then we sort the workers:

worker.sort()

Sorting workers lets us reuse previous work. When a stronger worker appears, all jobs considered for weaker workers remain possible.

We initialize:

total = 0
best = 0
j = 0

total stores the answer.

best stores the best profit among jobs available so far.

j points to the next job that has not been considered yet.

For each worker:

for ability in worker:

we add all newly available jobs:

while j < len(jobs) and jobs[j][0] <= ability:
    best = max(best, jobs[j][1])
    j += 1

After this loop, best is the best profit this worker can earn.

Then we add it:

total += best

Finally:

return total

returns the maximum total profit.

Testing

def run_tests():
    s = Solution()

    assert s.maxProfitAssignment(
        [2, 4, 6, 8, 10],
        [10, 20, 30, 40, 50],
        [4, 5, 6, 7],
    ) == 100

    assert s.maxProfitAssignment(
        [85, 47, 57],
        [24, 66, 99],
        [40, 25, 25],
    ) == 0

    assert s.maxProfitAssignment(
        [1, 2, 3],
        [10, 20, 30],
        [3, 3, 3],
    ) == 90

    assert s.maxProfitAssignment(
        [5, 1, 5],
        [50, 10, 60],
        [5],
    ) == 60

    assert s.maxProfitAssignment(
        [10],
        [100],
        [1, 10, 20],
    ) == 200

    print("all tests passed")

run_tests()

Test meaning: