Solution: Minimum Cost to Hire K Workers
Let’s solve the Minimum Cost to Hire K Workers problem using the Top K Elements pattern.
We'll cover the following
Statement
You are given
quality[i]
: Represents the work quality of theworker. wage[i]
: Represents the minimum wage expectation of theworker.
You want to hire exactly k
workers to form a paid group, and you must follow these payment rules:
Wage expectation: Every worker in the group must be paid at least their minimum wage expectation.
Proportional pay: The pay for each worker must be directly proportional to their quality. For example, if one worker’s quality is twice that of another, they must be paid twice as much.
Your goal is to determine the least amount of money required to hire exactly k
workers while satisfying the above conditions.
Constraints
n
quality.length
wage.length
k
n
quality[i]
,wage[i]
Solution
This solution uses the top k elements pattern, commonly used when selecting the top k
items based on a certain criterion. Here, we need to form a group of exactly k
workers and minimize the total cost while ensuring fair payments based on the workers’ wage expectations and quality. Below are some key observations that will help us to solve the problem:
Proportionality condition: All workers in the group must be paid proportionally to their quality. If one worker’s quality is twice that of another, they must be paid twice as much.
Wage-to-quality ratio: For each worker, we calculate a ratio that indicates how much we need to pay per unit of quality. This ratio is defined as:
Greedy approach: To minimize the total wage, we process workers based on their wage-to-quality ratios in ascending order. Once we select
k
workers, we fix the highest wage-to-quality ratio among them. All workers are paid according to this ratio, ensuring proportionality.Optimization using a heap: We can use a max heap to efficiently manage the total quality of selected workers. This allows us to keep track of the workers with the smallest total quality, which is important for minimizing the total wage. The max heap allows us to quickly access the largest quality (at the top of the heap) and remove it in constant time, ensuring that only
k
workers remain.
The steps of the algorithm are given below:
Creates a list of tuple
workers
for each worker. Sort these tuples based on the ratios in ascending order to process workers with the lowest ratio first. Each tuple contains:The worker’s wage-to-quality ratio (
w/q
)The worker’s quality (
q
)
Create a max heap
heap
to store the qualities of the selected workers.Initialize the below variables:
A variable
totalQuality
is used to track the total quality of the workers in the heapA variable
minCost
to store the minimum cost encountered during the process
Iterate through the sorted list of workers based on their ratios. For each worker:
Add their quality (as a negative value to simulate max heap behavior) to the
heap
.Update the
totalQuality
by adding the current worker’s quality.
After adding a worker, check if the
heap
contains more thank
workers. If so, remove the worker with the highest quality (i.e., the smallest negative value) to minimize the total quality used in cost calculations.Once the
heap
contains exactlyk
workers, compute the cost of hiring them. This is done by multiplying the highest wage-to-quality ratio (of the current worker) by thetotalQuality
of the selected group. Update theminCost
if the current one is lower than the previously recorded minimum.After processing all workers, return the
minCost
calculated.
Let’s look at the following illustration to get a better understanding of the solution:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.