# Solution For Minimum Cost To Hire K Workers

The “Minimum Cost to Hire K Workers” problem on Leetcode is a problem that provides a set of workers, each with their own respective hourly wage and a specified number of hours they can work. The goal is to hire k workers so that the total cost of hiring them is minimized, with the constraint that each worker must be paid their specified hourly wage.

To solve this problem, we can first sort the workers based on their hourly rate in ascending order. Then, we can iterate through each worker, maintaining a priority queue of up to k workers with the largest hourly rate. The priority queue should contain tuples of (hourly rate, hours worked) for each worker.

As we iterate through each worker, we add them to the priority queue if it has less than k elements. If it has k elements, we compute the total cost of hiring these k workers by finding the sum of their hourly rate multiplied by the total hours worked. If this cost is less than our current minimum cost, we update our minimum cost.

We continue iterating through the remaining workers and updating our minimum cost until all workers have been processed.

Below is a detailed solution in Python:

“`python
import heapq

def mincostToHireWorkers(quality, wage, k):
ratio = [float(w) / q for w, q in zip(wage, quality)] # sort workers by increasing hourly ratio
workers = sorted(zip(ratio, quality))
# initialize variables
total_quality, min_cost = 0, float(‘inf’)
heap = []

``````for r, q in workers:
# add worker to priority queue if it hasn't reached k yet
heapq.heappush(heap, -q)
total_quality += q

# remove worker with largest quality if heap is full
if len(heap) > k:
total_quality += heapq.heappop(heap)  # remove worker with highest quality

# calculate cost if k workers have been selected
if len(heap) == k:
min_cost = min(min_cost, total_quality * r)

return min_cost
``````

“`

The time complexity of this solution is O(n log n), where n is the number of workers. The space complexity is O(n), for storing the sorted workers and the priority queue.

## Step by Step Implementation For Minimum Cost To Hire K Workers

```There are N workers.  The i-th worker has a quality[i] and a minimum wage expectation wage[i].

Now we want to hire exactly K workers to form a paid group.  When hiring a group of K workers, we must pay them according to the following rules:

Every worker in the paid group should be paid in the ratio of their quality compared to other workers in the paid group.
Every worker in the paid group must be paid at least their minimum wage expectation.
Return the least amount of money needed to form a paid group satisfying the above conditions.

Example 1:

Input: quality = [10,20,5], wage = [70,50,30], K = 2
Output: 105.00000
Explanation: We pay 70 to 0-th worker and 35 to 2-th worker.
Example 2:

Input: quality = [3,1,10,10,1], wage = [4,8,2,2,7], K = 3
Output: 30.66667
Explanation: We pay 4 to 0-th worker, 13.33333 to 2-th and 3-th workers seperately.

Note:

1 <= K <= N <= 10000, where N = quality.length = wage.length
1 <= quality[i] <= 10000
1 <= wage[i] <= 10000
```There are N workers.  The i-th worker has a quality[i] and a minimum wage expectation wage[i].

Now we want to hire exactly K workers to form a paid group.  When hiring a group of K workers, we must pay them according to the following rules:

Every worker in the paid group should be paid in the ratio of their quality compared to other workers in the paid group.
Every worker in the paid group must be paid at least their minimum wage expectation.
Return the least amount of money needed to form a paid group satisfying the above conditions.

Example 1:

Input: quality = [10,20,5], wage = [70,50,30], K = 2
Output: 105.00000
Explanation: We pay 70 to 0-th worker and 35 to 2-th worker.
Example 2:

Input: quality = [3,1,10,10,1], wage = [4,8,2,2,7], K = 3
Output: 30.66667
Explanation: We pay 4 to 0-th worker, 13.33333 to 2-th and 3-th workers seperately.

Note:

1 <= K <= N <= 10000, where N = quality.length = wage.length
1 <= quality[i] <= 10000
1 <= wage[i] <= 10000
```There are N workers.  The i-th worker has a quality[i] and a minimum wage expectation wage[i].

Now we want to hire exactly K workers to form a paid group.  When hiring a group of K workers, we must pay them according to the following rules:

Every worker in the paid group should be paid in the ratio of their quality compared to other workers in the paid group.
Every worker in the paid group must be paid at least their minimum wage expectation.
Return the least amount of money needed to form a paid group satisfying the above conditions.

Example 1:

Input: quality = [10,20,5], wage = [70,50,30], K = 2
Output: 105.00000
Explanation: We pay 70 to 0-th worker and 35 to 2-th worker.
Example 2:

Input: quality = [3,1,10,10,1], wage = [4,8,2,2,7], K = 3
Output: 30.66667
Explanation: We pay 4 to 0-th worker, 13.33333 to 2-th and 3-th workers seperately.

Note:

1 <= K <= N <= 10000, where N = quality.length = wage.length
1 <= quality[i] <= 10000
1 <= wage[i] <= 10000
```There are N workers.  The i-th worker has a quality[i] and a minimum wage expectation wage[i].

Now we want to hire exactly K workers to form a paid group.  When hiring a group of K workers, we must pay them according to the following rules:

Every worker in the paid group should be paid in the ratio of their quality compared to other workers in the paid group.
Every worker in the paid group must be paid at least their minimum wage expectation.
Return the least amount of money needed to form a paid group satisfying the above conditions.

Example 1:

Input: quality = [10,20,5], wage = [70,50,30], K = 2
Output: 105.00000
Explanation: We pay 70 to 0-th worker and 35 to 2-th worker.
Example 2:

Input: quality = [3,1,10,10,1], wage = [4,8,2,2,7], K = 3
Output: 30.66667
Explanation: We pay 4 to 0-th worker, 13.33333 to 2-th and 3-th workers seperately.

Note:

1 <= K <= N <= 10000, where N = quality.length = wage.length
1 <= quality[i] <= 10000
1 <= wage[i] <= 10000
```using System;

public class Solution {

public double MincostToHireWorkers(int[] quality, int[] wage, int K) {

//To store the ratio of quality to wage
double[] ratio = new double[quality.Length];

for(int i = 0; i < quality.Length; i++)
{
ratio[i] = (double)wage[i] / quality[i];
}

//To sort the ratio array in ascending order
Array.Sort(ratio);

//To store the sum of first K elements of quality array
double sum = 0;

//To store the result
double result = double.MaxValue;

//To store the sum of first K elements of quality array
for(int i = 0; i < quality.Length; i++)
{
//To add current element to sum
sum += quality[i];

//If size of current window is K
if(i >= K - 1)
{
//Update the result if it is smaller than the current result
result = Math.Min(result, sum * ratio[i]);

//Remove the first element of the current window
sum -= quality[i - (K - 1)];
}
}

//Return the result
return result;
}
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]