LeetCode 826 - Most Profit Assigning Work
This problem asks us to maximize the total profit earned by assigning jobs to workers, under a specific rule: each worker can only perform jobs whose difficulty is less than or equal to their ability.
Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Binary Search, Greedy, Sorting
Solution
Problem Understanding
This problem asks us to maximize the total profit earned by assigning jobs to workers, under a specific rule: each worker can only perform jobs whose difficulty is less than or equal to their ability.
We are given three arrays:
difficulty[i]represents how difficult thei-thjob is.profit[i]represents how much money is earned by completing thei-thjob.worker[j]represents the ability level of thej-thworker.
A worker may perform at most one job, but the same job can be assigned to multiple workers. This is a very important detail because it changes the nature of the problem. We are not matching workers uniquely to jobs. Instead, every worker independently chooses the best possible job they can perform.
For each worker, we want to find the job with the highest profit among all jobs whose difficulty does not exceed the worker’s ability. If no such job exists, that worker contributes 0 profit.
The final answer is the sum of profits earned by all workers.
The constraints are:
1 <= n, m <= 10^41 <= difficulty[i], profit[i], worker[i] <= 10^5
These constraints are large enough that a naive O(n * m) solution may still pass in some languages, but it is not ideal and misses opportunities for optimization. Since sorting 10^4 elements is inexpensive, we should consider a solution involving sorting and efficient traversal.
There are several important edge cases to think about upfront.
A worker may be too weak to perform any job. In this case, their contribution should be 0.
Multiple jobs may have the same difficulty but different profits. We must ensure we always choose the most profitable one.
A harder job may actually pay less than an easier job. For example:
difficulty = [2, 4]
profit = [50, 20]
A worker with ability 4 should still choose the difficulty 2 job because it pays more. This means we cannot simply pick the highest difficulty job available. We need the maximum profit seen so far up to a worker’s ability.
The problem guarantees valid input sizes and positive values, so we do not need to handle empty arrays or invalid inputs.
Approaches
Brute Force Approach
The most straightforward solution is to process every worker independently.
For each worker, we iterate through all jobs and check whether the worker can complete that job. If they can, we compare its profit against the best profit seen so far.
At the end of scanning all jobs, we add the worker’s best possible profit to the total answer.
This works because every worker is independent. Since jobs may be repeated infinitely, there is no conflict between workers. We simply maximize each worker’s personal profit.
However, this approach becomes inefficient because for every worker we scan all jobs.
If there are m workers and n jobs, the total time complexity becomes:
O(n * m)
With 10^4 jobs and 10^4 workers, this can lead to 10^8 operations in the worst case, which is unnecessarily expensive.
Key Insight for an Optimal Solution
The important observation is that workers only care about:
The highest profit available for any difficulty less than or equal to their ability.
This suggests sorting.
If we sort jobs by difficulty and workers by ability, we can process both in ascending order using a two pointer strategy.
As we move through jobs, we maintain:
best_profit_so_far
This represents the maximum profit among all jobs that the current worker can perform.
Because workers are processed in sorted order, once a job becomes available for one worker, it remains available for all stronger workers.
This allows us to scan jobs only once, making the solution much faster.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n × m) | O(1) | Check every job for every worker |
| Optimal | O(n log n + m log m) | O(n) | Sort jobs and workers, then use two pointers |
Algorithm Walkthrough
Optimal Algorithm Using Sorting and Two Pointers
- Combine
difficultyandprofitinto a list of job pairs.
We create tuples of the form:
(difficulty, profit)
This lets us sort jobs while keeping their associated profits together. 2. Sort jobs by difficulty.
After sorting, jobs become ordered from easiest to hardest. This allows us to efficiently process which jobs become available as worker ability increases.
3. Sort the worker array.
Processing workers from weakest to strongest ensures that once we process a job for one worker, we never need to revisit it. 4. Initialize tracking variables.
We maintain:
job_index, pointing to the current jobbest_profit, storing the maximum profit among available jobstotal_profit, accumulating the final answer
- Process workers in increasing order.
For each worker:
- Move
job_indexforward while the worker can complete the job. - Update
best_profitwith the maximum profit encountered. - Add
best_profittototal_profit.
Since jobs are sorted, every job before job_index is guaranteed to be doable by the current worker.
6. Return total_profit.
After all workers are processed, we return the accumulated result.
Why it works
The algorithm maintains an important invariant:
best_profitalways represents the highest profit among all jobs the current worker can perform.
Since workers are processed in ascending order, the set of feasible jobs only grows. We never miss a valid job, and we never reconsider old jobs unnecessarily. Every worker receives the maximum possible profit independently, which guarantees the total profit is optimal.
Python Solution
from typing import List
class Solution:
def maxProfitAssignment(
self,
difficulty: List[int],
profit: List[int],
worker: List[int]
) -> int:
jobs = sorted(zip(difficulty, profit))
worker.sort()
total_profit = 0
best_profit = 0
job_index = 0
for ability in worker:
while (
job_index < len(jobs)
and jobs[job_index][0] <= ability
):
best_profit = max(
best_profit,
jobs[job_index][1]
)
job_index += 1
total_profit += best_profit
return total_profit
The implementation starts by pairing each job difficulty with its corresponding profit using zip(). We then sort these job pairs by difficulty so jobs become available in increasing order.
The worker array is also sorted so that workers are processed from weakest to strongest.
The variable job_index acts as a pointer into the sorted jobs list. As each worker is processed, we move this pointer forward and include every job they can complete.
Instead of storing every valid job, we only keep the single most valuable profit in best_profit. This is enough because workers only care about the maximum achievable profit.
For each worker, we add the best available profit to total_profit.
Since every job is visited at most once and every worker is processed once, the traversal after sorting is linear.
Go Solution
package main
import "sort"
func maxProfitAssignment(difficulty []int, profit []int, worker []int) int {
type Job struct {
difficulty int
profit int
}
n := len(difficulty)
jobs := make([]Job, n)
for i := 0; i < n; i++ {
jobs[i] = Job{
difficulty: difficulty[i],
profit: profit[i],
}
}
sort.Slice(jobs, func(i, j int) bool {
return jobs[i].difficulty < jobs[j].difficulty
})
sort.Ints(worker)
totalProfit := 0
bestProfit := 0
jobIndex := 0
for _, ability := range worker {
for jobIndex < len(jobs) &&
jobs[jobIndex].difficulty <= ability {
if jobs[jobIndex].profit > bestProfit {
bestProfit = jobs[jobIndex].profit
}
jobIndex++
}
totalProfit += bestProfit
}
return totalProfit
}
The Go implementation follows the same logic as the Python version, but uses a custom Job struct to pair difficulty and profit values together.
Sorting is handled with sort.Slice for jobs and sort.Ints for workers.
Unlike Python, Go does not provide tuple sorting directly, so using a struct keeps the implementation clean and readable.
Integer overflow is not a concern here because the maximum total profit is:
10^4 × 10^5 = 10^9
which safely fits inside Go's int type on standard LeetCode environments.
Worked Examples
Example 1
Input
difficulty = [2,4,6,8,10]
profit = [10,20,30,40,50]
worker = [4,5,6,7]
Step 1: Sort Jobs
| Difficulty | Profit |
|---|---|
| 2 | 10 |
| 4 | 20 |
| 6 | 30 |
| 8 | 40 |
| 10 | 50 |
Sorted workers:
[4,5,6,7]
Step 2: Process Workers
| Worker Ability | Newly Available Jobs | Best Profit | Total Profit |
|---|---|---|---|
| 4 | (2,10), (4,20) | 20 | 20 |
| 5 | none | 20 | 40 |
| 6 | (6,30) | 30 | 70 |
| 7 | none | 30 | 100 |
Final answer:
100
Example 2
Input
difficulty = [85,47,57]
profit = [24,66,99]
worker = [40,25,25]
Step 1: Sort Jobs
| Difficulty | Profit |
|---|---|
| 47 | 66 |
| 57 | 99 |
| 85 | 24 |
Sorted workers:
[25,25,40]
Step 2: Process Workers
| Worker Ability | Available Jobs | Best Profit | Total Profit |
|---|---|---|---|
| 25 | none | 0 | 0 |
| 25 | none | 0 | 0 |
| 40 | none | 0 | 0 |
Final answer:
0
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n log n + m log m) | Sorting dominates, the two pointer traversal is linear |
| Space | O(n) | Extra space for storing paired jobs |
The main cost comes from sorting the jobs and workers. After sorting, each job and worker is visited exactly once during the two pointer scan, making the traversal O(n + m).
Since we explicitly create a list of paired jobs, the algorithm uses O(n) extra memory.
Test Cases
sol = Solution()
assert sol.maxProfitAssignment(
[2, 4, 6, 8, 10],
[10, 20, 30, 40, 50],
[4, 5, 6, 7]
) == 100 # Example 1
assert sol.maxProfitAssignment(
[85, 47, 57],
[24, 66, 99],
[40, 25, 25]
) == 0 # Example 2
assert sol.maxProfitAssignment(
[5],
[100],
[5]
) == 100 # Single worker can do single job
assert sol.maxProfitAssignment(
[5],
[100],
[4]
) == 0 # Worker cannot do any job
assert sol.maxProfitAssignment(
[2, 4, 6],
[50, 20, 10],
[6]
) == 50 # Easier job pays more
assert sol.maxProfitAssignment(
[2, 2, 2],
[10, 20, 30],
[2]
) == 30 # Same difficulty, different profits
assert sol.maxProfitAssignment(
[1, 2, 3],
[10, 20, 30],
[1, 2, 3]
) == 60 # Exact matching difficulties
assert sol.maxProfitAssignment(
[1, 3, 5],
[10, 30, 50],
[10, 10]
) == 100 # Strong workers take best job
assert sol.maxProfitAssignment(
[100000],
[100000],
[100000]
) == 100000 # Maximum values
assert sol.maxProfitAssignment(
[1, 2, 3],
[5, 6, 7],
[1, 1, 1, 1]
) == 20 # Many workers repeating same job
| Test | Why |
|---|---|
| Example 1 | Validates normal behavior |
| Example 2 | Validates workers unable to perform jobs |
| Single job | Smallest valid input |
| Worker too weak | Ensures 0 profit handling |
| Easier job pays more | Verifies max-profit logic |
| Duplicate difficulty | Ensures best profit is selected |
| Exact difficulty match | Confirms boundary correctness |
| Very strong workers | Tests repeated job reuse |
| Maximum values | Validates constraint limits |
| Many identical workers | Confirms repeated assignment behavior |
Edge Cases
Workers Cannot Perform Any Job
A worker may have ability smaller than the minimum job difficulty. A naive implementation might accidentally assign an invalid job or produce incorrect profit.
For example:
difficulty = [10]
worker = [5]
The implementation handles this correctly because the while loop never executes, leaving best_profit = 0. That worker contributes zero profit.
Easier Jobs Can Pay More Than Harder Jobs
A common mistake is assuming workers should always choose the hardest available job.
Consider:
difficulty = [2, 4]
profit = [50, 20]
worker = [4]
The best answer is 50, not 20.
Our implementation handles this using the running maximum best_profit, which always stores the highest profit among all feasible jobs.
Duplicate Difficulties With Different Profits
Multiple jobs may share the same difficulty but offer different rewards.
For example:
difficulty = [5, 5, 5]
profit = [10, 20, 30]
worker = [5]
A buggy solution might stop at the first matching job.
Our implementation processes all jobs with allowable difficulty and continuously updates best_profit, ensuring the worker receives the highest possible reward.
Multiple Workers Performing the Same Job
Since jobs can be repeated infinitely, multiple workers may choose the same best-paying job.
For example:
difficulty = [2]
profit = [100]
worker = [2, 2, 2]
The correct answer is 300.
Our implementation naturally supports this because jobs are never removed or marked as used. Every worker independently receives the best available profit.