Most Profit Assigning Work

#6 Most AskedMedium

Most Profit Assigning Work #6 Most Asked

Medium

DoorDash

12 views

Topics:

ArraysGreedy AlgorithmsTwo Pointers

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 i^th job, and
worker[j] is the ability of j^th worker (i.e., the j^th 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⁴
1 <= difficulty[i], profit[i], worker[i] <= 10⁵

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the sizes of the `difficulty`, `profit`, and `worker` arrays? What is the maximum possible value for each element within these arrays?
Can the `difficulty` and `profit` arrays have different lengths? If so, what should I do if they don't correspond (e.g., `difficulty` has an element but `profit` doesn't at the same index)?
Is it possible for any of the input arrays (`difficulty`, `profit`, `worker`) to be empty or null?
If a worker cannot complete any job (i.e., their ability is less than the minimum difficulty), what should be returned? Should I return 0, or is there some other specified default?
If multiple jobs provide the same maximum profit for a worker, is there a preference for which job to assign (e.g., prioritize the job with the lowest difficulty)?

Brute Force Solution

Approach

The brute force strategy in this scenario involves trying every possible work assignment combination to find the one that yields the highest total profit. It's like exploring every road on a map to find the best route. We will check each possible pairing of workers to jobs to see what maximizes profit.

Here's how the algorithm would work step-by-step:

For each worker, consider assigning them to each available job one at a time.
Calculate the profit the worker would make if assigned to that specific job.
If we can assign one worker to a job, then figure out how to assign remaining workers to jobs.
Repeat this for all possible combinations of workers to jobs.
For each complete assignment of workers to jobs, calculate the total profit.
Keep track of the highest total profit found so far across all assignments.
After exploring every possible combination, the highest total profit that was kept track of is the final answer.

Code Implementation

def max_profit_assigning_work_brute_force(difficulty, profit, worker):
    maximum_profit = 0

    def calculate_maximum_profit(current_worker_index, current_profit):
        nonlocal maximum_profit

        # Base case: all workers have been assigned
        if current_worker_index == len(worker):
            maximum_profit = max(maximum_profit, current_profit)
            return

        # Iterate through all possible jobs for the current worker
        for job_index in range(len(difficulty)):
            # Check if the worker is capable of doing the job
            if worker[current_worker_index] >= difficulty[job_index]:

                # Recursively call the function for the next worker
                calculate_maximum_profit(
                    current_worker_index + 1,
                    current_profit + profit[job_index],
                )

    # Initiate the recursive calls to check every possible assignment
    calculate_maximum_profit(0, 0)

    return maximum_profit

Big(O) Analysis

Time Complexity

O(n!) – The described brute force approach explores all possible assignments of workers to jobs. Assuming 'n' is the number of workers (and potentially the number of jobs if we assume each worker is assigned a job), the algorithm essentially generates all permutations of worker-job assignments. Generating all permutations of n items takes n! (n factorial) operations because for the first worker, there are n job choices, for the second (n-1) choices, and so forth, leading to n * (n-1) * (n-2) * ... * 1 combinations. Therefore, the time complexity is O(n!).

Space Complexity

O(W!) – The brute force approach explores all possible assignments of workers to jobs. In the worst-case scenario, if we have W workers and enough jobs, the recursion depth can go up to W, representing assigning each worker one by one. At each level of the recursion, we potentially need to store information about the current assignment, leading to a recursion tree with W! (W factorial) branches in the worst case where each worker can be assigned to a different job. This translates to a space complexity of O(W!) due to the call stack and the storage of intermediate assignment states. N, in this context is indirectly relevant as it dictates the size of W (number of workers) which directly impacts the O(W!).

Optimal Solution

Approach

To maximize profit, we need to match people to jobs they can do, giving priority to the highest-paying jobs. We'll use a smart strategy to quickly find the best profit without checking every possible job assignment. This approach hinges on sorting and making locally optimal choices.

Here's how the algorithm would work step-by-step:

First, combine the difficulty and potential profit of each job into a single package for easier handling.
Next, sort the jobs by their profit, so we know the best-paying jobs are at the top.
Now, sort the people by their skill level; the most skilled people are at the top.
Go through each person, starting with the most skilled.
For each person, find the best job they can do (the one with the highest profit) that is within their skill range.
Instead of checking all available jobs each time, remember the maximum profit seen so far from all jobs that require less or the same difficulty as the current person's skill.
Add that maximum profit to the total profit.
By always choosing the highest-paying job available to each person based on their skill and previously seen jobs, you ensure maximum profit is earned.

Code Implementation

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

    # Sort jobs by profit to prioritize better paying ones.
    jobs.sort(key=lambda x: x[1])

    worker.sort()
    total_profit = 0
    maximum_profit_so_far = 0
    job_index = 0

    # Iterate through workers, assigning them the best possible job.
    for skill in worker:
        while job_index < len(jobs) and jobs[job_index][0] <= skill:
            # Keep track of the maximum profit we can get
            maximum_profit_so_far = max(maximum_profit_so_far, jobs[job_index][1])
            job_index += 1

        # Add the maximum profit attainable for this worker.
        total_profit += maximum_profit_so_far

    return total_profit

Big(O) Analysis

Time Complexity

O(n log n + m log m) – The algorithm first combines difficulty and profit into job packages, which takes O(n) where n is the number of jobs. Sorting these jobs by profit takes O(n log n) time. Sorting the people by skill level takes O(m log m) time, where m is the number of people. Iterating through each person and finding the best job they can do involves a single pass, but the key optimization is remembering the maximum profit seen so far. Therefore, the dominant operations are the sorting steps, leading to a total time complexity of O(n log n + m log m).

Space Complexity

O(N) – The algorithm creates a list of job difficulty and profit pairs, which takes O(N) space where N is the number of jobs. Sorting this list in place doesn't change this space complexity, but the creation of this list itself is O(N). Although the people array is sorted in place, the job list persists, meaning the auxiliary space required is proportional to the number of jobs.

Edge Cases

Case	How to Handle
Empty difficulty, profit, or worker array	Return 0 if any of the input arrays are empty, as no profit can be made.
difficulty and profit arrays have different lengths	Return 0, or throw an IllegalArgumentException, as job mapping is impossible.
worker array is very large while difficulty/profit are small	The solution should scale efficiently by pre-processing jobs (difficulty/profit) to reduce search space.
All workers have very low ability, no job can be done.	The algorithm should return 0, since no worker can be assigned.
All jobs have same difficulty but different profits.	The solution must select the job with the highest profit if the worker is able to perform it.
All jobs have the same profit.	The solution should assign jobs with lowest difficulties (that worker is able to perform).
Integer overflow when calculating total profit for very large inputs	Use long to store the accumulated profit or modulo operation to prevent overflow if needed.
Duplicate worker abilities.	Handle duplicate worker abilities correctly by considering all possible job assignments for each worker.

Empty difficulty, profit, or worker array

How to Handle:

Return 0 if any of the input arrays are empty, as no profit can be made.

difficulty and profit arrays have different lengths

How to Handle:

Return 0, or throw an IllegalArgumentException, as job mapping is impossible.

worker array is very large while difficulty/profit are small

How to Handle:

The solution should scale efficiently by pre-processing jobs (difficulty/profit) to reduce search space.

All workers have very low ability, no job can be done.

How to Handle:

The algorithm should return 0, since no worker can be assigned.

All jobs have same difficulty but different profits.

How to Handle:

The solution must select the job with the highest profit if the worker is able to perform it.

All jobs have the same profit.

How to Handle:

The solution should assign jobs with lowest difficulties (that worker is able to perform).

Integer overflow when calculating total profit for very large inputs

How to Handle:

Use long to store the accumulated profit or modulo operation to prevent overflow if needed.

Duplicate worker abilities.

How to Handle:

Handle duplicate worker abilities correctly by considering all possible job assignments for each worker.