Problem Description

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 each element consists of two integers: tasks[i][0] represents the skill requirement needed to complete a task, and tasks[i][1] represents the profit earned from completing that task.

Each worker can complete at most one task, and they can only take a task if their skill level matches the task's skill requirement. An additional worker joins, who can take any task, regardless of the skill requirement.

The goal is to determine the maximum total profit that can be earned by optimally assigning the tasks to the workers.

Intuition

To maximize the profit, we must optimally assign tasks to workers based on their skills. A natural way to tackle this is to categorize available tasks by their skill requirements using a hash table. This allows quick access to tasks a particular worker can complete. For each worker, access the list of tasks they qualify for (if any exist) and assign them the task with the highest profit. This is done using a priority queue where tasks are sorted by profit in descending order.

Once all workers have been processed, there might still be tasks left unassigned. Here, the special worker, who can take any remaining task, should be used to take the task with the highest profit among the remaining options. This ensures that the maximum total profit is obtained from available tasks.

The solution is efficient as it focuses on matching workers to tasks with careful consideration of the profit, using data structures that enable both fast insertion and retrieval of maximum values.

Learn more about Greedy, Sorting and Heap (Priority Queue) patterns.

Solution Approach

To solve this problem optimally, we utilize a hash table with priority queues, allowing us to efficiently organize and access tasks based on skill requirements:

1. Hash Table for Task Grouping: We create a dictionary d where each key is a skill requirement and the associated value is a priority queue. This allows us to quickly find all tasks for a given skill level. We use SortedList for maintaining the profits in descending order.

2. Populate the Hash Table: For each available task, determined by its skill requirement and profit, append the task's profit to the corresponding skill key in the dictionary. If multiple tasks have the same skill requirement, they will be sorted in descending order of profit.

3. Assign Tasks to Workers: Iterate through each worker's skill level. For every skill, check if there are available tasks:

   • If tasks are available, remove the task with the highest profit (using pop()) and add the profit to the total accumulated profit.
   • This ensures that the worker takes the highest available profit task they can handle.

4. Utilize the Additional Worker: After assigning tasks to all regular workers, review the remaining tasks. Use the additional worker to complete the task with the highest profit from any remaining tasks, adding this profit to the total.

5. Final Calculations: Combine all gathered profits for the solution, ensuring you've maximized the output.

The implementation using these strategies efficiently optimizes the task assignment process, maximizing overall profit. Here’s how the code is structured:

class Solution:
    def maxProfit(self, workers: List[int], tasks: List[List[int]]) -> int:
        d = defaultdict(SortedList)
        for skill, profit in tasks:
            d[skill].add(profit)
      
        ans = 0
        for skill in workers:
            if not d[skill]:
                continue
            ans += d[skill].pop()
      
        mx = 0
        for ls in d.values():
            if ls:
                mx = max(mx, ls[-1])
      
        ans += mx
        return ans

This approach effectively makes use of data structures that ensure fast retrieval and updates, making it well-suited for this problem of maximizing task assignment profits.

Example Walkthrough

Let's walk through an example to understand the solution approach.

Suppose we have the following input:

• workers = [3, 4]
• tasks = [[3, 100], [3, 150], [4, 200], [5, 300]]

1. Hash Table for Task Grouping:

   • Initialize a dictionary d with keys representing skill levels and values as sorted lists of profits.
   • Populate d:
     • For task [3, 100], add 100 to d[3].
     • For task [3, 150], add 150 to d[3], resulting in d[3] = [150, 100].
     • For task [4, 200], add 200 to d[4], resulting in d[4] = [200].
     • For task [5, 300], add 300 to d[5], resulting in d[5] = [300].

2. Assign Tasks to Workers:

   • Initialize ans = 0 to accumulate profits.
   • Iterate over the workers array:
     • Worker with skill 3:
       • d[3] is not empty, take the highest profit by removing 150 from d[3].
       • Add 150 to ans, making ans = 150.
     • Worker with skill 4:
       • d[4] is not empty, take the highest profit by removing 200 from d[4].
       • Add 200 to ans, making ans = 350.

3. Utilize the Additional Worker:

   • Iterate over remaining tasks in d to find the maximum profit task:
     • d[3] has [100].
     • d[5] has [300].
   • The maximum profit is 300.
   • Add 300 from that task to ans, making the total ans = 650.

4. Final Calculation:

   • The total maximum profit earned by assigning tasks is 650.

Through this example, we've shown how to optimally assign tasks to workers and utilize an additional worker to maximize profits. The algorithm efficiently handles task assignments using a combination of hash tables and sorted lists.

Solution Implementation

Time and Space Complexity

The time complexity of the code is O((n + m) \times \log m), where n is the number of workers and m is the number of tasks. This complexity arises from the operations on the SortedList, which has logarithmic time complexity for insertion and deletion. Since each worker can attempt to take the highest profit task available to them and there is an additional pass through the list of tasks to find the maximum remaining profit, the operations performed on the SortedList make the overall complexity O((n + m) \times \log m).

The space complexity of the code is O(m). This is due to the creation of a defaultdict of SortedList instances, each potentially holding up to m profits (since each task's profit gets added to the corresponding skill level list).

Learn more about how to find time and space complexity quickly.