## Algorithm

Problem Name: 857. Minimum Cost to Hire K Workers

There are `n` workers. You are given two integer arrays `quality` and `wage` where `quality[i]` is the quality of the `ith` worker and `wage[i]` is the minimum wage expectation for the `ith` worker.

We want to hire exactly `k` workers to form a paid group. To hire a group of `k` workers, we must pay them according to the following rules:

1. Every worker in the paid group should be paid in the ratio of their quality compared to other workers in the paid group.
2. Every worker in the paid group must be paid at least their minimum wage expectation.

Given the integer `k`, return the least amount of money needed to form a paid group satisfying the above conditions. Answers within `10-5` of the actual answer will be accepted.

Example 1:

```Input: quality = [10,20,5], wage = [70,50,30], k = 2
Output: 105.00000
Explanation: We pay 70 to 0th worker and 35 to 2nd 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 0th worker, 13.33333 to 2nd and 3rd workers separately.
```

Constraints:

• `n == quality.length == wage.length`
• `1 <= k <= n <= 104`
• `1 <= quality[i], wage[i] <= 104`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``start coding...``
Copy The Code &

Input

cmd
Input: quality = [10,20,5], wage = [70,50,30], k = 2

Output

cmd
105.00000

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
double mincostToHireWorkers(vector& quality, vector& wage, int K) {
double res = INT_MAX;
int n = quality.size();
vector>workers;
for (int i = 0; i < n; ++i) {
workers.push_back({(double)wage[i]/quality[i], quality[i]});
}
sort(workers.begin(), workers.end());
int sum = 0;
priority_queuepq;
for (auto& x: workers) {
sum += x;
pq.push(x);
if (pq.size() > K) {
sum -= pq.top();
pq.pop();
}
if (pq.size() == K) {
res = min(res, x * sum);
}
}
return res;
}
};
``````
Copy The Code &

Input

cmd
Input: quality = [10,20,5], wage = [70,50,30], k = 2

Output

cmd
105.00000

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public double mincostToHireWorkers(int[] quality, int[] wage, int K) {
int n = quality.length;
Worker[] workers = new Worker[n];
for (int i = 0; i < n; i++) {
workers[i] = new Worker(quality[i], wage[i]);
}
Arrays.sort(workers);
double ans = 1e9;
int sum = 0;
PriorityQueue pool = new PriorityQueue<>();
for (Worker worker : workers) {
pool.offer(-worker.quality);
sum += worker.quality;
if (pool.size() > K) {
sum += pool.poll();
}
if (pool.size() == K) {
ans = Math.min(ans, sum * worker.ratio());
}
}
return ans;
}
}

class Worker implements Comparable {
int quality;
int wage;

public Worker(int quality, int wage) {
this.quality = quality;
this.wage = wage;
}

public double ratio() {
return (double) wage / quality;
}

public int compareTo(Worker other) {
return Double.compare(ratio(), other.ratio());
}
}
``````
Copy The Code &

Input

cmd
quality = [3,1,10,10,1], wage = [4,8,2,2,7], k = 3

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const mincostToHireWorkers = function(quality, wage, K) {
const workers = [], n = quality.length;
for (let i = 0; i < n; i++) {
workers[i] = { ratio: wage[i] / quality[i], quality: quality[i] }
}
workers.sort((a, b) => a.ratio - b.ratio);
const heap = new MaxPriorityQueue({ priority: x => x.quality });
let totalQuality = 0, res = Infinity;
while (workers.length) {
const curWorker = workers.shift();
totalQuality += curWorker.quality;
heap.enqueue(curWorker);

if (heap.size() > K) {
totalQuality -= heap.dequeue().element.quality;
}
if (heap.size() === K) {
res = Math.min(res, curWorker.ratio * totalQuality)
}
}
return res;
};
``````
Copy The Code &

Input

cmd
quality = [3,1,10,10,1], wage = [4,8,2,2,7], k = 3

Output

cmd
30.66667

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def mincostToHireWorkers(self, quality, wage, K):
workers, res, heap, sumq = sorted((w / q, q, w) for q, w in zip(quality, wage)), float("inf"), [], 0
for ratio, q, w in workers:
heapq.heappush(heap, -q)
sumq += q
if len(heap) > K:
sumq += heapq.heappop(heap)
if len(heap) == K:
res = min(res, ratio * sumq)
return res
``````
Copy The Code &

Input

cmd
quality = [10,20,5], wage = [70,50,30], k = 2

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
using System;
using System.Collections.Generic;

namespace LeetCode
{
public class _0857_MinimumCostToHireKWorkers
{
public double MincostToHireWorkers(int[] quality, int[] wage, int K)
{
var workers = new List();
for (int i = 0; i < quality.Length; i++)
workers.Sort();

var pool = new Heap(K);
var qualityTotal = 0;
var result = double.MaxValue;
foreach (var worker in workers)
{
pool.Offer(-worker.Quality);
qualityTotal += worker.Quality;

if (pool.Size() > K)
{
var maxQualityWorker = -1 * pool.Poll();
qualityTotal -= (int)maxQualityWorker;
}
if (pool.Size() == K)
{
result = Math.Min(result, qualityTotal * worker.Ratio);
}
}
return result;
}

public class Worker : IComparable
{
public Worker(int quality, int wage)
{
Quality = quality;
Wage = wage;
}

public int Quality { get; set; }

public int Wage { get; set; }

public double Ratio { get { return Wage * 1.0 / Quality; } }

public int CompareTo(Worker other)
{
return Ratio.CompareTo(other.Ratio);
}
}

public class Heap
{
double[] heap = null;
int size = 0;

public Heap(int k)
{
heap = new double[k + 1];
}

public int Size()
{
return size;
}

public void Offer(double val)
{
heap[size++] = val;
HeapifyUp();
}

public double Peek()
{
if (size == 0) throw new InvalidOperationException();
return heap;
}

public double Poll()
{
if (size == 0) throw new InvalidOperationException();
double resp = heap;
if (size > 1)
{
heap = heap[size - 1];
HeapifyDown();
}

size--;
return resp;
}

private void HeapifyUp()
{
int index = size - 1;
while (HasParent(index))
{
int parentIndex = GetParentIndex(index);
if (heap[parentIndex] > heap[index])
Swap(parentIndex, index);
else
break;

index = parentIndex;
}
}

private void HeapifyDown()
{
int index = 0;
while (HasLeftChild(index))
{
int left = GetLeftChildIndex(index), right = GetRightChildIndex(index), minIndex = left;
double min = heap[left];
if (HasRightChild(index) && heap[right] < min)
{
min = heap[right];
minIndex = right;
}

if (heap[index] > min)
Swap(index, minIndex);
else
break;

index = minIndex;
}
}

private void Swap(int index1, int index2)
{
double temp = heap[index1];
heap[index1] = heap[index2];
heap[index2] = temp;
}

private bool HasParent(int index)
{
return (index + 1) / 2 - 1 >= 0;
}

private bool HasLeftChild(int index)
{
return index * 2 + 1 < size;
}

private bool HasRightChild(int index)
{
return index * 2 + 2 < size;
}

private int GetParentIndex(int index)
{
return (index + 1) / 2 - 1;
}

private int GetLeftChildIndex(int index)
{
return index * 2 + 1;
}

private int GetRightChildIndex(int index)
{
return index * 2 + 2;
}
}
}
}
``````
Copy The Code &

Input

cmd
quality = [10,20,5], wage = [70,50,30], k = 2

Output

cmd
105.00000