You are given an integer array workers, where workers[i] represents the skill level of the ith worker. You are also given a 2D integer array tasks, where:
tasks[i][0] represents the skill requirement needed to complete the task.tasks[i][1] represents the profit earned from completing the task.Each worker can complete at most one task, and they can only take a task if their skill level is equal to the task's skill requirement. An additional worker joins today who can take up any task, regardless of the skill requirement.
Return the maximum total profit that can be earned by optimally assigning the tasks to the workers.
Example 1:
Input: workers = [1,2,3,4,5], tasks = [[1,100],[2,400],[3,100],[3,400]]
Output: 1000
Explanation:
Example 2:
Input: workers = [10,10000,100000000], tasks = [[1,100]]
Output: 100
Explanation:
Since no worker matches the skill requirement, only the additional worker can complete task 0.
Example 3:
Input: workers = [7], tasks = [[3,3],[3,3]]
Output: 3
Explanation:
The additional worker completes task 1. Worker 0 cannot work since no task has a skill requirement of 7.
Constraints:
1 <= workers.length <= 1051 <= workers[i] <= 1091 <= tasks.length <= 105tasks[i].length == 21 <= tasks[i][0], tasks[i][1] <= 109Problem Overview: You are given tasks with a difficulty and profit, along with workers that each have a maximum capability. A worker can complete any task whose difficulty is less than or equal to their ability. The goal is to assign tasks so the total profit earned from all workers is maximized.
Approach 1: Brute Force Worker Scan (O(n * m) time, O(1) space)
The most direct strategy checks every task for each worker. For a worker with ability w, iterate through the entire task list and track the highest profit where difficulty[i] ≤ w. Repeat this scan for every worker and accumulate the best profit found. This approach uses simple array iteration and requires no extra data structures. However, the nested iteration makes it expensive when both the number of tasks and workers are large.
Approach 2: Greedy Sorting + Hash Table + Priority Queue (O((n + m) log n) time, O(n) space)
The efficient solution sorts tasks by difficulty and processes workers from the least capable to the most capable. As you iterate through workers, push the profits of all tasks whose difficulty is ≤ the worker’s ability into a max heap (priority queue). The heap always stores profits of tasks the current worker can complete.
For each worker, the maximum profit available is simply the top of the heap. Add that value to the total profit. Since tasks are inserted into the heap only once and workers are processed in sorted order, this becomes a clean greedy strategy: each worker takes the best currently available task they can handle. Sorting both arrays ensures we never revisit tasks unnecessarily, and the heap efficiently tracks the best profit candidate.
This method dramatically reduces redundant work compared to brute force. Each task enters the heap once, and each worker performs at most one heap lookup. The result is O((n + m) log n) time with O(n) extra space.
Recommended for interviews: Interviewers expect the greedy sorting approach with a max heap. The brute force method shows you understand the constraint relationship between workers and tasks, but it does not scale. The priority queue solution demonstrates the correct use of sorting, greedy selection, and heap data structures to keep the best available profit accessible in logarithmic time.
Since each task can only be completed by a worker with a specific skill, we can group the tasks by skill requirements and store them in a hash table d, where the key is the skill requirement and the value is a priority queue sorted by profit in descending order.
Then, we iterate through the workers. For each worker, we find the corresponding priority queue in the hash table d based on their skill requirement, take the front element (i.e., the maximum profit the worker can earn), and remove it from the priority queue. If the priority queue is empty, we remove it from the hash table.
Finally, we add the maximum profit from the remaining tasks to the result.
The time complexity is O((n + m) times log m), and the space complexity is O(m). Where n and m are the number of workers and tasks, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Worker Scan | O(n * m) | O(1) | Small inputs or when demonstrating the baseline logic in interviews |
| Greedy Sorting + Priority Queue | O((n + m) log n) | O(n) | General case with large inputs where tasks and workers must be processed efficiently |
Practice Maximize Profit from Task Assignment with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor