Most Profit Assigning Work

Patrick Leaton
Published: Dec. 17, 2021, 7:02 p.m.
Problem Description

You have n jobs and m workers. You are given three arrays: difficulty, profit, and worker where:

  • difficulty[i] and profit[i] are the difficulty and the profit of the ith job, and
  • worker[j] is the ability of jth worker (i.e., the jth worker can only complete a job with difficulty at most worker[j]).

Every worker can be assigned at most one job, but one job can be completed multiple times.

  • For example, if three workers attempt the same job that pays $1, then the total profit will be $3. If a worker cannot complete any job, their profit is $0.

Return the maximum profit we can achieve after assigning the workers to the jobs.

 

Example 1:

Input: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
Output: 100
Explanation: Workers are assigned jobs of difficulty [4,4,6,6] and they get a profit of [20,20,30,30] separately.

Example 2:

Input: difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25]
Output: 0

 

Constraints:

  • n == difficulty.length
  • n == profit.length
  • m == worker.length
  • 1 <= n, m <= 10^4
  • 1 <= difficulty[i], profit[i], worker[i] <= 10^5

 

The description was taken from https://leetcode.com/problems/most-profit-assigning-work/.

Problem Solution

#O(N(Log(N)) + W(Log(W))) Time, O(N) Space
#N is size of difficulty and profit, W is size of worker
class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        max_profit, last_worker, best_pay = 0, 0, 0
        jobs = []
       
        for i in range(len(difficulty)):
            jobs.append((difficulty[i], profit[i]))
        jobs = sorted(jobs)
       
        for ability in sorted(worker):
            for i in range(last_worker, len(jobs)):
                if ability < jobs[i][0]:
                    break
                best_pay = max(best_pay, jobs[i][1])
                last_worker += 1
            max_profit += best_pay
           
        return max_profit

Problem Explanation

A brute force approach to this question would be to walk each worker through each difficulty that they are qualified for, save the job with the maximum profit, then add that to the total maximum profit for each worker.

However, that would require O(N*W) time.

Let's think about a better approach like this. 

Let's say we worked at a company where each numbered task was up for grabs to employees with correlated experience, and each employee is only interested in earning the most profit for their years of experience.  We walked in with ten years of experience.  Our coworker walked up to us and told us how much money they made with nine years of experience.  If we wanted to know how much money we could make with our ten years of experience, at that point, we wouldn't need to consider the maximum profit of jobs for years one through nine because our coworker just told us that.  We could instead take their information and begin considering jobs that require ten or more years of experience, starting from their level of experience and the maximum amount of money they were able to make from it, saving ourselves the hassle of revisiting that range.

What we can do to solve this problem is sort the list of difficulties with the correlated profits, sort the list of workers, then traverse the list of workers and exhaust each upper-bound range of jobs that they are qualified for to find the maximum profit for them.  Before we begin walking a worker through their jobs, however, we will note the last job they were qualified to work and the maximum profit they were able to make from the jobs they considered.  That will allow us to create a baseline to start from which we can pad our lower bound.  This will save us from repeating work.  

This would be considered a greedy approach because we are sorting our input to prioritize tasks so that we may conserve resources.  

Let's start by initializing our maximum profit output, the ability of the previous worker, and the best pay that the last worker was able to get with their ability.

        max_profit, last_worker, best_pay = 0, 0, 0

 

We will also create a list of jobs.

        jobs = []

 

For each job difficulty and their correlated profit, we will append them to the jobs list and sort them based on difficulty.

        for i in range(len(difficulty)):
            jobs.append((difficulty[i], profit[i]))
        jobs = sorted(jobs)

 

Then, we will sort the list of workers and begin walking each worker through the list of jobs they are qualified for so that we may find the maximum profit each worker can make with their respective range of options.

        for ability in sorted(worker):

 

For each worker, we will begin looking at jobs starting from the last worker before them.

            for i in range(last_worker, len(jobs)):

 

If we find that the current worker isn't qualified for the current job we are considering, we will break.

                if ability < jobs[i][0]:
                    break

 

Otherwise, we will compare the best pay the previous worker was able to get and the pay of the current job, updating the best pay if it is greater.

                best_pay = max(best_pay, jobs[i][1])

 

Once we have done that, we will increment the last worker value, essentially saying that we have now considered jobs that require an additional year of ability so we shouldn't revisit this current ability level anymore in the future.

                last_worker += 1

 

When we have considered each upper-bound range of jobs for the current employee, we will increment the maximum profit output by the best pay they were able to find.

            max_profit += best_pay

 

After we have a cumulative maximum profit for each worker, all we need to do now is return that maximum profit.

        return max_profit