Domain 2MediumMEDIUM

Most Profit Assigning Work

Assign each worker the highest-paying job they can perform by sorting jobs and workers, using a running maximum profit pointer.

Domain: medium•Updated: 2026-09-01
#Greedy#Sorting#Two Pointers

Problem Breakdown

We are given two arrays representing jobs (difficulty, profit) and an array of workers with specific ability levels. Each worker can perform at most one job, provided the job’s difficulty is less than or equal to their ability level. Crucially, a single job type (defined by its index) can be performed multiple times across different workers; however, for any given assignment instance, we want to maximize profit per worker.

Inputs:

  • difficulty: List of integers representing the skill required for each job.
  • profit: Corresponding list of integer profits for those jobs.
  • worker: List of integers representing ability levels of available workers.

Output:

  • A single integer: The maximum total profit achievable by optimally assigning all possible work to the workforce.

Intuition

A brute-force approach would iterate through every worker and check every job to find the highest-paying one they can perform. This results in a time complexity of O(M⋅K)O(M \cdot K), where MM is the number of workers and KK is the number of jobs. Given constraints up to 10,000 for both arrays, this could reach ≈108\approx 10^8 operations per test case, which risks Time Limit Exceeded (TLE).

Key Insight: If a worker can perform Job A with difficulty DAD_A, they might also be able to perform any job with difficulty <DA< D_A. Since we want the maximum profit for that ability level, it doesn’t matter if there are multiple jobs available; only the one yielding the highest profit among all reachable difficulties matters.

This suggests a monotonic property: as worker ability increases, the set of accessible jobs grows (or stays same), and the maximum achievable profit is non-decreasing with respect to difficulty thresholds. By sorting both the job list by difficulty and the workers by ability, we can use two pointers or a linear scan approach where we maintain a running max_profit for all jobs encountered so far that are within reach of the current worker’s ability.

Approach

  1. Combine Data: Zip difficulty and profit into pairs to keep them synchronized during sorting.
  2. Sort Jobs: Sort these job pairs by difficulty in ascending order. This allows us to process jobs from easiest to hardest.
  3. Pre-process Profits (Implicit): As we iterate through the sorted workers, for each worker’s ability level, there might be multiple jobs they can do. We want the best one available up to that point. Instead of storing a complex lookup table, we maintain a current_max_profit variable while advancing our pointer in the job list.
  4. Sort Workers: To utilize two pointers efficiently (linear scan), sort the workers by ability ascending as well. This ensures that when we move from one worker to the next with higher or equal ability, we only need to advance through the sorted job list once more; we never look back at lower-difficulty jobs because their profit potential is already captured in our running maximum.
  5. Two Pointers Logic:
    • Initialize job_idx = 0 and current_max_profit = 0.
    • Iterate through each worker (sorted).
    • While the job at job_idx has difficulty ≤\le current worker’s ability: update current_max_profit with that job’s profit, then increment job_idx. This ensures current_max_profit holds the highest pay for any job within this worker’s capability.
    • Add current_max_profit to total result (if no jobs are reachable yet, it remains 0).

Complexity Analysis

  • Time Complexity: O(Nlog⁡N+Mlog⁡M)O(N \log N + M \log M), where NN is the number of jobs and MM is the number of workers. This comes from sorting both arrays. The subsequent linear scan using two pointers takes O(N+M)O(N + M). Given constraints (10410^4), this fits well within typical time limits (usually ≈108\approx 10^8 ops/sec).
  • Space Complexity: Python’s sorted and zip create new lists, so technically O(N)O(N) auxiliary space is required to store the sorted job pairs. This is acceptable given memory constraints for inputs of size N=104N=10^4.

Solution

def maxProfitAssignment(difficulty: list[int], profit: list[int], worker: list[int]) -> int:
    # Combine difficulty and profit into a single sorted structure by difficulty
    jobs = sorted(zip(difficulty, profit))
    
    # Sort workers to enable linear two-pointer traversal
    workers_sorted = sorted(worker)
    
    total_profit = 0
    current_max_profit = 0
    job_idx = 0
    
    n_jobs = len(jobs)
    
    for w in workers_sorted:
        # Advance the job pointer as long as the worker can handle the difficulty
        while job_idx < n_jobs and jobs[job_idx][0] <= w:
            current_max_profit = max(current_max_profit, jobs[job_idx][1])
            job_idx += 1
        
        # Add the best profit available for this ability level (or 0 if none)
        total_profit += current_max_profit
        
    return total_profit

# Example usage matching problem description:
# difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
# Output should be 100.

Edge Cases Handled

  • Worker Ability < Minimum Job Difficulty: The while loop condition fails immediately (jobs[job_idx][0] <= w is false), leaving current_max_profit at its initial value of 0, correctly adding 00 to the total for that worker.
  • Duplicate Difficulties/Profits: Sorting handles duplicates naturally; if multiple jobs have same difficulty but different profits, we take the max during the loop iteration before moving past them or updating current_max_profit. If a higher profit job appears later with equal difficulty (impossible in stable sort of pairs unless explicitly handled), our logic ensures we capture the highest seen so far.
  • Empty Inputs: Constraints state lengths ≥1\ge 1, but if they were empty, loops would not execute and return 00 correctly.
  • Large Profits/Summation: Python handles arbitrary precision integers automatically, preventing overflow issues common in fixed-width integer languages like C++ or Java for this specific problem’s constraints (N=104×105=109N=10^4 \times 10^5 = 10^9, fits in standard int anyway).