Skip to main content
Talentd

Maximize Profit from Task Assignment - Solution & Explanation

MediumPremiumFree on FleetCodeArrayGreedySortingHeap (Priority Queue)9 min read
Practice this problem

Problem Statement

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:

  • Worker 0 completes task 0.
  • Worker 1 completes task 1.
  • Worker 2 completes task 3.
  • The additional worker completes task 2.

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 <= 105
  • 1 <= workers[i] <= 109
  • 1 <= tasks.length <= 105
  • tasks[i].length == 2
  • 1 <= tasks[i][0], tasks[i][1] <= 109

Approach Overview

Problem 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.

Solution

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Worker ScanO(n * m)O(1)Small inputs or when demonstrating the baseline logic in interviews
Greedy Sorting + Priority QueueO((n + m) log n)O(n)General case with large inputs where tasks and workers must be processed efficiently

Frequently Asked Questions

Is Maximize Profit from Task Assignment easy or hard?
Maximize Profit from Task Assignment is generally considered a Medium difficulty problem. The brute force idea is straightforward, but identifying the greedy ordering and using a priority queue to track the best available profit requires familiarity with sorting and heap-based optimization.
Maximize Profit from Task Assignment Python/Java solution
Most implementations follow the same pattern: sort tasks by difficulty, iterate workers in sorted order, and push eligible profits into a max heap. Python typically uses heapq (with negated values for a max heap), while Java uses PriorityQueue with a reverse comparator. The algorithm remains O((n + m) log n) across languages.
What is the best approach for Maximize Profit from Task Assignment?
The most efficient solution uses a greedy strategy with sorting and a max heap (priority queue). Sort tasks by difficulty and workers by ability, then push eligible task profits into the heap as workers become capable of performing them. Each worker selects the highest profit available. This runs in O((n + m) log n) time and O(n) space.
Is Maximize Profit from Task Assignment asked at Google/Amazon/Meta?
Greedy assignment problems involving sorting and heaps are common in interviews at companies like Amazon, Google, and Meta. Variants of worker-task matching and profit maximization appear frequently because they test understanding of greedy strategies, sorting, and priority queues.
What data structure is used in Maximize Profit from Task Assignment?
The key data structure is a max heap (priority queue) used to track the highest profit among tasks that a worker can perform. Sorting arrays and sometimes hash tables for grouping tasks are also used to efficiently organize the data before heap processing.
What is the time complexity of Maximize Profit from Task Assignment?
The optimal solution runs in O((n + m) log n) time, where n is the number of tasks and m is the number of workers. Sorting tasks and workers takes O(n log n + m log m), and heap operations for inserting and retrieving profits add logarithmic overhead. Space complexity is O(n) for the priority queue.
How to solve Maximize Profit from Task Assignment in O((n + m) log n)?
Sort tasks by difficulty and workers by ability. Traverse workers from smallest ability to largest while pushing profits of all tasks they can perform into a max heap. The heap top represents the highest profit available for that worker. Add that value to the total profit and continue until all workers are processed.

Ready to solve this problem?

Practice Maximize Profit from Task Assignment with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays