We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Most Profit Assigning Work

Number: 853

Difficulty: Medium

Paid? No

Companies: DoorDash, Amazon, Microsoft, NetEase

Problem Description

Given a set of jobs where each job has a certain difficulty and profit, and a list of workers where each worker has an ability, the goal is to assign each worker at most one job such that the worker’s ability is greater than or equal to the job difficulty. A job can be performed by multiple workers. Return the maximum total profit that can be earned by optimally assigning jobs to workers.

Key Insights

  • Pair each job's difficulty and profit and sort them by difficulty.
  • Compute a running maximum of profit for increasing difficulties; this allows you to quickly determine the best profit available for any worker ability.
  • For each worker, use binary search in the sorted job list to find the highest difficulty job they can perform.
  • Sum the best profits for all workers, handling workers that cannot perform any job by adding zero.

Space and Time Complexity

Time Complexity: O(n log n + m log n), where n is the number of jobs and m is the number of workers. Space Complexity: O(n), used for storing and processing the sorted job pairs and the running max profit list.

Solution

The solution involves first pairing up job difficulties with their respective profits and then sorting these pairs based on difficulty. As you process this sorted list, maintain a running maximum profit to ensure that at any given difficulty level, you know the best profit you can earn from any job up to that difficulty. For each worker, perform a binary search on the sorted job difficulties to quickly determine the best profit that the worker can achieve. By summing these values for all workers, you achieve the maximum total profit. This algorithm leverages sorting, prefix maximum, and binary search to efficiently compute the result.

Code Solutions

# Python solution with detailed comments

import bisect

def maxProfitAssignment(difficulty, profit, worker):
    # Pair up difficulty and profit for jobs and sort by difficulty
    jobs = sorted(zip(difficulty, profit))
    
    max_profit_up_to = []
    current_max = 0
    # Create a list of difficulties and update max profit seen so far.
    difficulties = []
    for d, p in jobs:
        current_max = max(current_max, p)
        difficulties.append(d)
        max_profit_up_to.append(current_max)
    
    total_profit = 0
    # For each worker, binary search for the most difficult job they can work on
    for ability in worker:
        # bisect_right returns insertion point, subtract 1 to get valid index
        idx = bisect.bisect_right(difficulties, ability) - 1
        if idx >= 0:
            total_profit += max_profit_up_to[idx]
    return total_profit

# Example usage:
# print(maxProfitAssignment([2,4,6,8,10], [10,20,30,40,50], [4,5,6,7]))
← Back to All Questions