Most Profit Assigning Work - Leetcode Solution

The Most Profit Assigning Work problem on LeetCode asks us to find the maximum total profit that can be earned by assigning tasks to workers. We are given three arrays: difficulty, profit, and worker. The difficulty array contains the difficulty levels of the tasks, the profit array contains the profits that can be earned for each task, and the worker array contains the maximum difficulty level that each worker can handle.

To solve this problem, we first need to sort the tasks by their difficulty level. Then, we create a list of tuples where each tuple contains two elements: the difficulty level of the task and its corresponding profit. We sort this list of tuples by the profit in descending order.

Next, we iterate through the list of tuples and for each task, we find the worker who can handle the task by iterating through the worker array. We select the first worker who can handle the task and add the corresponding profit to our total profit.

We repeat this process for all the tasks and return the total profit as the answer.

Here's the Python code to solve the problem:

def maxProfitAssignment(difficulty, profit, worker):
    tasks = sorted(zip(difficulty, profit))
    worker.sort()
    
    i = j = total_profit = max_profit = 0
    
    while i < len(worker):
        while j < len(tasks) and tasks[j][0] <= worker[i]:
            max_profit = max(max_profit, tasks[j][1])
            j += 1
        total_profit += max_profit
        i += 1
        
    return total_profit

In this code, we first sort the tasks by their difficulty level. Then we sort the worker array.

We then use two pointers, i and j to keep track of the worker and task indices respectively. We also initialize variables total_profit and max_profit to 0.

We iterate over the worker array. For each worker, we iterate over the tasks until we find a task that the worker can handle. We keep track of the maximum profit of all the tasks that the worker can handle.

Once we find all the tasks that the worker can handle, we add the maximum profit to the total profit.

Finally, we return the total profit as the answer.

1