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.

Description Hints 3 Solution Video 11:50

3476. Maximize Profit from Task Assignment

Medium65.9% acceptancePremium elsewhere, free here

You are given an integer array workers, where workers[i] represents the skill level of the i^th 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 <= 10⁵
1 <= workers[i] <= 10⁹
1 <= tasks.length <= 10⁵
tasks[i].length == 2
1 <= tasks[i][0], tasks[i][1] <= 10⁹

Topics

Hints open one at a time

Hint 1

Use a hashmap to group the tasks by their required skill level tasks[i][0]

Hint 2

For each worker, assign the highest profit task from the hashmap that matches their exact skill requirement

Hint 3

Assign the task with the maximum profit among the unassigned tasks to the extra worker

11:50

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[1,2,3,4,5]
[[1,100],[2,400],[3,100],[3,400]]

Input

[10,10000,100000000]
[[1,100]]

Input

[7]
[[3,3],[3,3]]

Your code is saved on this device.Solution