algoadvance

You are given two integer arrays difficulty and profit where difficulty[i] and profit[i] indicate the difficulty and profit of the iᵗʰ job, and an integer array worker where worker[j] is the skill level of the jᵗʰ worker.

Return the maximum profit we can achieve, given that each worker can be assigned at most one job and the job assigned to the worker has a difficulty less than or equal to the worker’s skill level.

Clarifying Questions

  1. Can workers be assigned the same job?
    • Yes, multiple workers can be assigned the same job if they qualify for it.
  2. Is there a limit on the number of jobs?
    • No explicit limit specified, but algorithm efficiency will depend on handled constraints.
  3. What should be the output if no worker can be assigned a job?
    • The output should be 0.

Strategy

To solve this problem optimally, we can:

  1. Sort Jobs: Combine difficulty and profit into a list of tuples and sort them based on difficulty. This allows easier assignment of maximum profitable jobs to workers.
  2. Sort Workers: Sort the worker array to perform an efficient assignment.
  3. Two-Pointers Technique: Use two pointers - one to traverse the sorted worker array and the other to traverse the jobs array - to ensure that each worker gets the highest profit job they can do.

We will iterate through the workers in ascending order of their skills, maintaining the maximum profit seen so far from the available jobs they can perform.

Time Complexity

Thus, the overall time complexity is (O(n \log n + m \log m)).

Code

def maxProfitAssignment(difficulty, profit, worker):
    # Combine difficulty and profit into a list of tuples
    jobs = sorted(zip(difficulty, profit))
    # Sort the worker array
    worker.sort()

    max_profit = 0
    max_assignable_profit = 0
    job_index = 0
    n = len(jobs)
    
    for w in worker:
        # Update the max profit for all jobs that this worker can do
        while job_index < n and jobs[job_index][0] <= w:
            max_assignable_profit = max(max_assignable_profit, jobs[job_index][1])
            job_index += 1
        # Add the best profit that this worker can achieve
        max_profit += max_assignable_profit
    
    return max_profit

# Example usage
difficulty = [2, 4, 6, 8, 10]
profit = [10, 20, 30, 40, 50]
worker = [4, 5, 6, 7]
print(maxProfitAssignment(difficulty, profit, worker))  # Output: 100

Explanation of the Code

  1. Combine difficulty and profit into jobs: We zip and sort them.
  2. Sort the worker array: To ensure we are processing the least skilled workers first.
  3. Initialize pointers and max profit trackers:
    • max_profit to store total profit.
    • max_assignable_profit to store the best profit for the current worker’s skill.
  4. Iterate through workers:
    • For each worker, update max_assignable_profit to be the maximum profit they can achieve.
    • Sum up the highest achievable profits for all workers.

This solution ensures each worker is assigned the best job they can do with a time complexity of (O(n \log n + m \log m)).

Try our interview co-pilot at AlgoAdvance.com