#826

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Most Profit Assigning Work

Assign workers to jobs maximizing total profit using difficulty, profit, and worker arrays efficiently with binary search pattern.

array two pointers binary search greedy sorting

Problem Statement

You are given three integer arrays: difficulty, profit, and worker. Each index in difficulty and profit represents a job with a certain difficulty and associated profit. Each worker can perform at most one job, but a job can be assigned to multiple workers if their abilities allow.

Your task is to assign workers to jobs to maximize total profit. Each worker can only do jobs with difficulty less than or equal to their ability, and the goal is to return the maximum achievable profit after all assignments.

Examples

Example 1

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

Output: 100

Workers are assigned jobs of difficulty [4,4,6,6] and they get a profit of [20,20,30,30] separately.

Example 2

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

Output: 0

Example details omitted.

Constraints

n == difficulty.length
n == profit.length
m == worker.length
1 <= n, m <= 104
1 <= difficulty[i], profit[i], worker[i] <= 105

Solution Approach

Sort jobs by difficulty and track max profit

Combine difficulty and profit into pairs and sort by difficulty. As you iterate, replace each profit with the maximum seen so far. This ensures when assigning a job to a worker, we always select the best profit within their ability range.

Use binary search for each worker

For each worker, perform a binary search on the sorted difficulty array to locate the hardest job they can complete. Retrieve the corresponding maximum profit efficiently, avoiding linear scans that would exceed time limits for large arrays.

Sum profits for all workers

Iterate over the worker array and accumulate profits from the jobs they can complete using the precomputed maximum profit array. This guarantees the total profit is maximized according to the binary search assignment pattern.

Complexity Analysis

Metric	Value
Time	O(n + m + maxAbility)
Space	O(maxAbility)

Time complexity is O(n + m + maxAbility) because sorting and cumulative max calculation is linear with respect to the maximum difficulty, and each worker lookup is done via binary search. Space complexity is O(maxAbility) to store the cumulative maximum profits up to each difficulty level.

What Interviewers Usually Probe

You are expected to optimize for large arrays of workers and jobs.
Binary search over difficulty to find suitable jobs is crucial for efficiency.
Sorting jobs and precomputing maximum profits indicates correct greedy assignment logic.

Common Pitfalls or Variants

Common pitfalls

Assuming each worker must get a unique job instead of allowing repeated job assignments.
Forgetting to maintain cumulative maximum profit while iterating sorted jobs.
Using linear search per worker instead of binary search, leading to timeouts on large inputs.

Follow-up variants

Change worker array to allow multiple jobs per worker, requiring dynamic programming.
Limit the number of times a job can be assigned, adding constraint handling.
Replace profit array with profit functions depending on worker skill, increasing algorithmic complexity.

FAQ

What is the main strategy for Most Profit Assigning Work?

Sort jobs by difficulty, compute cumulative max profits, and assign each worker using binary search to find the best job they can perform.

Can a job be assigned to multiple workers?

Yes, a single job can be completed by multiple workers if their abilities meet or exceed the job's difficulty.

What is the time complexity of the optimal solution?

The solution runs in O(n + m + maxAbility) time due to sorting, cumulative max computation, and binary search for each worker.

Why is binary search used in this problem?

Binary search efficiently finds the hardest job a worker can complete, replacing slower linear scans and ensuring maximum profit selection.

What are common mistakes when implementing this solution?

Common errors include not using cumulative max profits, using linear search per worker, and incorrectly restricting jobs to one worker each.

terminal

Solution

Solution 1: Sorting + Two Pointers

We can sort the jobs in ascending order of ability, and then sort the jobs in ascending order of difficulty.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def maxProfitAssignment(
        self, difficulty: List[int], profit: List[int], worker: List[int]
    ) -> int:
        worker.sort()
        jobs = sorted(zip(difficulty, profit))
        ans = mx = i = 0
        for w in worker:
            while i < len(jobs) and jobs[i][0] <= w:
                mx = max(mx, jobs[i][1])
                i += 1
            ans += mx
        return ans

Solution 2: Dynamic Programming

Let's denote $m = \max(\textit{difficulty})$ and define an array $f$ of length $m + 1$, where $f[i]$ represents the maximum profit among jobs with difficulty less than or equal to $i$, initially $f[i] = 0$.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def maxProfitAssignment(
        self, difficulty: List[int], profit: List[int], worker: List[int]
    ) -> int:
        worker.sort()
        jobs = sorted(zip(difficulty, profit))
        ans = mx = i = 0
        for w in worker:
            while i < len(jobs) and jobs[i][0] <= w:
                mx = max(mx, jobs[i][1])
                i += 1
            ans += mx
        return ans

Continue Practicing

#611 valid triangle number #825 friends of appropriate ages #786 k th smallest prime fraction