LeetCode 826: Most Profit Assigning Work

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 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</code>, then the total profit will be <code>$ 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⁵

Difficulty: Medium

Tags: array, two pointers, binary search, greedy, sorting

Rating: 93.36%

Solution

Here’s my Python solution to this problem:

#Problem 826: Most Profit Assigning Work

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        jobs = list(zip(difficulty, profit))
        jobs.sort()
        worker.sort()

        i = 0  # Index for jobs
        max_profit = 0 
        total_profit = 0 
        n = len(jobs)
        
        for ability in worker:
            while i < n and jobs[i][0] <= ability:
                max_profit = max(max_profit, jobs[i][1])
                i += 1
            
            total_profit += max_profit
        
        return total_profit

Complexity Analysis

The solution has the following complexity characteristics:

Time Complexity: $O(n²)$
Space Complexity: $O(1)$

Note: This is an automated analysis and may not capture all edge cases or specific algorithmic optimizations.