Abstract / Summary

Pick k workers paying each at least their ratio times the highest paid and find the lowest total cost possible.

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 64% (200k+ submissions).

Typical patterns to solve this problem:

• Array
• Greedy
• Heap (Priority Queue)
• Sorting

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 “minimum cost to hire exactly k workers” problem. Each worker is described by a quality value and a minimum wage expectation. The algorithm selects a group of k workers such that the total wage paid is minimized while respecting two constraints: every worker receives at least their minimum wage, and all workers are paid a common wage-to-quality ratio. The solution proceeds by sorting workers according to their quality-to-wage ratio, then iteratively maintaining a candidate set of the k smallest qualities using a max-heap. At each step the current ratio determines the total cost for the current candidate set, and the minimum across all steps is returned.

Key Steps

The first logical block builds a list of tuples that capture each worker’s ratio, quality, and wage. The ratio is computed as quality / wage, which is the inverse of the more common wage-to-quality ratio; sorting by this value in descending order ensures that the smallest ratio encountered so far is always the current worker’s ratio.

candidates = [ ( q/w, q, w ) for q, w in zip (quality, wage) ]
candidates.sort(reverse = True)

A max-heap (current) stores the qualities of the workers that are currently being considered for the group. The variable sum tracks the total quality of the workers inside the heap. As the algorithm iterates over the sorted candidates, each worker’s quality is added to sum and the negative quality is pushed onto the heap to simulate a max-heap using Python’s heapq (which implements a min-heap).

current = []
sum     = 0
for ratio, q, w in candidates:
    sum += q
    heappush(current, -q)   # max-heap via negative values

When the heap size exceeds k, the worker with the largest quality (the most expensive when scaled by the current ratio) is removed. This removal reduces sum accordingly, guaranteeing that the heap always contains the k smallest qualities seen so far.

if len(current) > k:
    remove = -heappop(current)
    sum   -= remove

Whenever the heap size exactly equals k, the current ratio represents the lowest quality-to-wage ratio among the selected workers. The total cost for this configuration is computed as sum / ratio, and the global minimum (result) is updated if this cost is lower.

if len(current) == k:
    result = min(result, sum / ratio)

Finally, after processing all candidates, the algorithm returns the smallest total cost found.

return result

Edge Cases

The algorithm gracefully handles the situation where k equals the total number of workers. In that case the heap never exceeds size k, so no removal occurs, and the cost is computed once using the ratio of the last processed worker, which is the smallest ratio among all workers.

When k is 1, each iteration creates a heap of size one, and the cost calculation reduces to q / (q/w) = w, effectively returning the smallest wage among all workers, which satisfies the constraints.

If multiple workers share the same quality-to-wage ratio, the sorting order preserves their original relative positions, but the heap logic still ensures that only the smallest qualities are retained, so the algorithm remains correct regardless of duplicate ratios.

The use of float('inf') as the initial result guarantees that any feasible cost will replace it, even when the first valid group of k workers appears late in the iteration.

Performance Optimizations

The most significant optimization is the use of a max-heap to keep track of the k smallest qualities while iterating through the sorted list. By pushing negative qualities, the code leverages Python’s built-in min-heap implementation without needing a custom data structure. This approach ensures that each insertion and removal operation runs in logarithmic time relative to k, keeping the overall processing efficient as the algorithm scans the entire candidate list only once.

Sorting the workers by their quality-to-wage ratio up front reduces the problem to a single pass over a monotonic sequence of ratios. Because the ratio only decreases (due to the descending sort), the current ratio at any iteration is guaranteed to be the minimum ratio for the workers currently in the heap, eliminating the need for additional scans or recomputation of ratios.

The cumulative sum variable avoids recomputing the total quality of the heap on each iteration. By updating sum incrementally when workers are added or removed, the algorithm eliminates an O(k) aggregation step, further contributing to its efficiency.

Overall, the combination of a single sort, a bounded heap, and incremental aggregation yields a solution that scales well with the size of the input arrays while adhering strictly to the problem constraints.

Imagine you have a big team of helpers who all want to be paid for their hard work. Each helper has a quality score that shows how well they work and a minimum wage they need. Some helpers are very fast, while others take a bit more time.

The goal is to pick a group of helpers to finish a job. There are two rules. The first rule is that if you pick a group, everyone must get paid the same amount of money for each point of quality they have. The second rule is that every single person must get at least the minimum wage they asked for.

To solve this, the code first looks at every helper and figures out their specific ratio of quality versus the money they expect. By looking at these ratios, it becomes clear how much you have to pay everyone in the group to keep them all happy.

Then, the code starts a little game of picking helpers. It sorts them so that it looks at the most efficient ones first. As it goes through the list, it adds helpers to a group one by one and keeps track of the total quality points they bring.

If the group gets too big, the code looks at all the helpers currently in the group and says goodbye to the one who has the highest quality points. This is because high quality points are expensive when you have to pay the higher group rate. By keeping only the best group of helpers for each ratio, it finds the smallest amount of money needed to pay everyone fairly. Once it checks all the possible groups, it knows the cheapest way to get the job done.

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			Python		Go
	LeetcodeHelp	C++		Java			Python
	Progiez	C++		Java			Python
github	BigEggStudy				C#
	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fengvyi	C++
	JoshCrozier		JS
	keineahnung2345	C++
	ruoru					Rust
	suxrobGM				C#
	trung-hn						Python
	varunu28			Java
	vli02							C
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fengvyi	C++
JoshCrozier	JavaScript
keineahnung2345	C++
ruoru	Rust
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
wisdompeak	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