Algorithm
Problem Name: 857. Minimum Cost to Hire K Workers
Problem Link: https://leetcode.com/problems/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:
- 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.
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.length1 <= k <= n <= 1041 <= quality[i], wage[i] <= 104
Code Examples
#1 Code Example with C Programming
Code -
C Programming
start coding...Input
Input: quality = [10,20,5], wage = [70,50,30], k = 2
Output
105.00000
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int K) {
double res = INT_MAX;
int n = quality.size();
vector < vector<double>>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_queue < int>pq;
for (auto& x: workers) {
sum += x[1];
pq.push(x[1]);
if (pq.size() > K) {
sum -= pq.top();
pq.pop();
}
if (pq.size() == K) {
res = min(res, x[0] * sum);
}
}
return res;
}
};
Input
Input: quality = [10,20,5], wage = [70,50,30], k = 2
Output
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 < Integer> 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 < Worker> {
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());
}
}
Input
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;
};
Input
quality = [3,1,10,10,1], wage = [4,8,2,2,7], k = 3
Output
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
Input
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 < Worker>();
for (int i = 0; i < quality.Length; i++)
workers.Add(new Worker(quality[i], wage[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 < Worker>
{
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[0];
}
public double Poll()
{
if (size == 0) throw new InvalidOperationException();
double resp = heap[0];
if (size > 1)
{
heap[0] = 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;
}
}
}
}
Input
quality = [10,20,5], wage = [70,50,30], k = 2
Output
105.00000