Abstract / Summary

Assign workers to jobs to maximize profit minus cost, each worker can do at most one job and each job given to at most one worker.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 56% (400k+ submissions).

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the classic assignment problem where each worker can perform at most one job, and each job can be assigned to at most one worker. The goal is to maximize total profit while respecting the difficulty constraint of each job relative to a worker’s ability. The algorithm proceeds by ordering jobs by profitability, ordering workers by skill, and then greedily matching the most skilled workers with the most profitable jobs they can handle.

Data Preparation

The first step transforms the parallel profit and difficulty arrays into a single heap structure that can deliver the highest-profit job quickly. By negating the profit values, the standard heapq min-heap is repurposed as a max-heap.

jobs = [ (-p, d) for p, d in zip(profit, difficulty) ]   # pair profit (negated) with difficulty
heapify(jobs)                                            # O(n) heap construction

This preparation consolidates the two input lists into a priority queue where the element at the root always represents the currently most profitable job among those still under consideration.

Worker Processing Loop

Workers are sorted in descending order of ability so that the most capable workers are considered first. This ordering guarantees that when a worker is examined, any job that remains in the heap is already feasible for that worker or for a less skilled worker later in the loop.

result = 0
for w in sorted(worker, reverse=True):
    while jobs and jobs[0][1] > w:
        heappop(jobs)                     # discard jobs too difficult for this worker
    if not jobs:
        break                             # no remaining jobs can be assigned
    p, d = jobs[0]                        # peek at most profitable feasible job
    result += -p                           # add its profit (undo negation)

The inner while loop removes jobs whose difficulty exceeds the current worker’s ability, ensuring that the heap’s top element is always assignable. The if not jobs guard handles the situation where all remaining jobs are too hard for any subsequent worker, allowing the algorithm to exit early.

Edge Cases

The code gracefully handles several boundary conditions without additional checks. When the profit or difficulty lists are empty, the initial heap is empty, the outer loop never enters the profit-adding branch, and the function returns zero. If the worker list is empty, the for loop is skipped entirely, also yielding a zero profit. Workers whose skill level is lower than the minimum job difficulty simply trigger the inner while loop until the heap is empty, after which the early break prevents further unnecessary iterations. Duplicate skill levels among workers do not affect correctness because each iteration processes a worker independently, and the heap state reflects only the jobs still available.

Performance Optimizations

Two primary optimizations are evident. First, the use of a heap to keep the most profitable job at the top eliminates the need to scan the entire job list for each worker, reducing the per-worker selection cost to logarithmic heap operations. Second, sorting workers in descending order enables early termination: once the heap becomes empty, the algorithm stops processing remaining workers, avoiding wasted work. The combination of a single heap construction (heapify) and a single sort of the workers ensures that the heavy lifting is performed only once, and subsequent operations are confined to efficient heap pushes and pops. The negation of profit values to simulate a max-heap with the built-in min-heap implementation avoids the overhead of a custom comparator, leveraging the highly optimized native heap functions.

Imagine a playground where there is a big pile of jobs to do and a group of friends who want to help out. Each job has a certain level of difficulty to finish and a bag of gold coins as a reward. Each friend has a different amount of strength, so some friends can only manage the easier jobs while others are strong enough to take on the harder ones.

This code acts like a helper who wants to make sure everyone gets the best reward possible. First, the jobs are organized so that the ones with the most gold coins are looked at first. Then, the strongest friend is picked to see which of the most valuable jobs they can handle. If the job is too hard for that friend, it is set aside because they are not strong enough to do it. If the friend is strong enough, they take the job and collect the gold coins. This continues with the next strongest friend until all the friends have had a turn or until there are just no jobs left that anyone can finish. It is a way of matching up the right people with the right work to collect as much gold as possible.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java				Python	TS
	WalkCCC	C++		Java				Python
	leetcode.ca	C++		Java			Go	Python	TS
	LeetcodeHelp	C++		Java				Python
	Progiez	C++		Java				Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fengvyi	C++
	fsq	C++
	halfrost						Go
	JoshCrozier		JS
	lzl124631x	C++
	ruoru					Rust
	shreymehul				C#
	suxrobGM				C#
	varunu28			Java
	wisdompeak	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fengvyi	C++
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
lzl124631x	C++
ruoru	Rust
shreymehul	C#
suxrobGM	C#
varunu28	Java
wisdompeak	C++
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality