Most Profit Assigning Work: Greedy Job Assignment

Most Profit Assigning Work (LeetCode 826) asks you to assign jobs to workers for maximum total profit. Each worker has an ability level and can only handle jobs at or below that difficulty. Every worker picks at most one job, but multiple workers can pick the same job. The trick is figuring out the best job for each worker without brute-forcing through every combination.

The problem

You are given three arrays:

• difficulty[i] and profit[i] describe job i. It takes difficulty[i] effort and pays profit[i].
• worker[j] describes the ability of worker j. A worker can only do a job where difficulty[i] <= worker[j].

Each worker can be assigned at most one job, but the same job can be assigned to multiple workers. Return the maximum total profit across all workers.

Example: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]

Worker with ability 4 can handle jobs with difficulty <= 4. The best such job pays 20. Worker with ability 5 can also only reach jobs up to difficulty 4 (there is no job with difficulty 5), so they also earn 20. Workers 6 and 7 can reach the job with difficulty 6, earning 30 each. Total: 20 + 20 + 30 + 30 = 100.

The key insight

Sorting unlocks everything. If you sort the jobs by difficulty and sort the workers by ability, you can sweep through both arrays with a single pointer. As you process workers from weakest to strongest, you only need to advance through jobs, never go backward. Along the way, you track the maximum profit seen so far.

This works because a stronger worker can do everything a weaker worker can, plus more. The best profit available to worker j is at least as good as the best profit available to any weaker worker.

The running maximum is what handles the tricky edge case where a harder job might pay less than an easier one. You are not looking for the profit of the hardest reachable job. You are looking for the best profit among all reachable jobs.

The solution

def maxProfitAssignment(difficulty, profit, worker):
    jobs = sorted(zip(difficulty, profit))
    worker.sort()

    j = 0
    best = 0
    total = 0

    for ability in worker:
        while j < len(jobs) and jobs[j][0] <= ability:
            best = max(best, jobs[j][1])
            j += 1
        total += best

    return total

The outer loop processes each worker. The inner while loop advances through sorted jobs as long as their difficulty is within the current worker's ability. Because both arrays are sorted, the job pointer j never resets. Each job is visited at most once across all workers.

Visual walkthrough

Let's trace through difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7].

The job pointer advances just enough for each worker and never backtracks. By the time we finish all four workers, the pointer has moved from 0 to 2, visiting only three jobs total across all iterations. That is the power of the two-pointer technique on sorted data.

Complexity analysis

Here n is the number of jobs and m is the number of workers. The sorting dominates.

The building blocks

This problem combines two fundamental building blocks that appear across many greedy and two-pointer problems.

Sort to create order, then sweep

Sorting transforms a messy assignment problem into a linear scan. Once jobs are sorted by difficulty, you can walk through them left to right, and each worker only needs to pick up where the last one left off. This same idea powers Merge Intervals (sort by start, sweep and merge), Meeting Rooms (sort by start, check overlaps), and 3Sum (sort the array, then converge two pointers).

Running maximum with two pointers

The running maximum lets you decouple "which jobs can this worker reach" from "which reachable job pays the most." Without it, you would need binary search or a separate pass for each worker. With it, one pointer handles both questions. This pattern shows up any time you need the best value in a growing prefix of sorted data.

Edge cases

All jobs are too hard. If every difficulty[i] exceeds every worker[j], the job pointer never advances and best stays at 0. Total profit is 0.

Harder jobs with lower profit. Consider difficulty = [5,10], profit = [50,10]. The job with difficulty 10 pays less than the one with difficulty 5. The running max handles this correctly. After scanning both jobs, best is still 50 (from the easier job), not 10.

All workers have the same ability. The job pointer advances once for the first worker and stays put for the rest. Every worker gets the same best value. The two-pointer approach handles this naturally with no special case.

Single worker, single job. The smallest possible input. The while loop checks if the one job fits, sets best if it does, and adds it to total. Correct with no edge-case code.

From understanding to recall

The algorithm is short, but the moving parts matter. Do you sort jobs by difficulty or by profit? Does the job pointer reset for each worker? Is it <= or < when comparing difficulty to ability?

Each of those decisions has a reason, and forgetting any one of them leads to a wrong answer. The fix is spaced repetition. Write the solution from memory, verify it, then revisit it in a few days. After a few reps, the sort-sweep-max pattern becomes automatic, and you can apply it to any problem where sorted order lets you avoid redundant work.

Related posts

• Two Sum II - Input Array Is Sorted - Another problem where sorting enables a two-pointer sweep instead of brute force
• Meeting Rooms II - Greedy scheduling with sorting and a sweep, using a min heap instead of a running max
• Merge Intervals - The foundational sort-then-sweep pattern for interval problems

Assigning jobs for maximum profit comes down to sorting and sweeping. Once you see that the running maximum handles mismatched difficulty-profit pairs, the two-pointer approach writes itself. Drill it until the sort order, pointer logic, and max tracking are automatic.