Minimum Cost to Hire K Workers

Difficulty Level Hard
Frequently asked in Google
HeapViews 3715

In minimum cost to hire K workers problem, we have given N workers from which we want to hire exactly k workers to form a paid group.  The i-th worker has a quality[i] and a minimum wage expectation wage[i].

Pay will be given to 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.

Example

Input: quality = [50, 30, 10, 60, 70], wage = [100, 120, 130, 90, 140], K = 3

Output: 360

Key points for Minimum Cost to Hire K Workers

Let’s say we have, quality =  [a,b,c,d] and wage = [p,q,r,s]

  • Effective ratio of quality with respect to first element will be : [1,b/a,c/a,d/a]
  • Effective wages be : [p , pb/a , pc/a, pd/a]
  • To ensure minimum wages to form a paid group of k workers with selecting ith element when jth element is considered for the proportion: B[i] <= (A[i] / A[j]) * B[j] == B[i] / A[i] <= B[j] / A[j] i.e., to satisfy the condition ratio of quality / min wage ratio should be arranged in descending order and all the subsequent ratio jth worker will automatically satisfy the minimum wage condition when considering the ith element.
  • For the optimal solution: say (b/cr + r + d/cr) is equivalent of writing : (b+c +d) * (r/c) i.e., the minimum sum of qualities multiplied by proportional factor is the solution. We already have the r/c in descending order O(nlogn).
  • Starting from the n-k-1 element means last k elements are minimum available elements from the perspective of the (n-k)th element. Maintain a max heap of these numbers (- min heap == max heap). As we see a number smaller than the max of min k elements: we just remove the max and insert the new element.
  • As soon as the new smaller element is detected: heap is updated and a new potential minimum sum is checked.

Implementation for Minimum Cost to Hire K Workers

C++ Program

#include<bits/stdc++.h>
using namespace std;
double hireKworkers(vector<int>& quality, vector<int>& wage, int K) {
    int N = quality.size();
    vector<pair<double, int>> vec;
    for(int i = 0; i < N; i++) {
        vec.push_back(make_pair(wage[i] * 1.0 / quality[i], quality[i])); 
    } 
    sort(vec.begin(), vec.end(), [](auto& a, auto& b){
        return a.first < b.first;
    });
    int quality_cnt = 0;
    priority_queue<int> q;
    for(int i = 0; i < K; i++) {
        quality_cnt += vec[i].second;
        q.push(vec[i].second);
    }
    double ans = quality_cnt * vec[K - 1].first;
    for(int i = K; i < N; i++) {
        q.push(vec[i].second);
        quality_cnt += vec[i].second;
        quality_cnt -= q.top();
        q.pop();
        ans = min(ans, quality_cnt * vec[i].first);
    }
    return ans;
}

int main(){
    int n=5;
    vector<int> quality ={50, 30, 10, 60, 70};
    vector<int> wages = {100, 120, 130, 90, 140};
    int k=3;
    cout<<"The least amount of money needed to form a paid group: "<<hireKworkers(quality,wages,k);
}
The least amount of money needed to form a paid group: 360

JAVA Program

import java.util.*;
class Main { 
    public static double hireKworkers(int[] quality, int[] wage, int K) {
        double[][] workers = new double[quality.length][2];
        PriorityQueue<Double> heap = new PriorityQueue<>(Comparator.reverseOrder());
        double sum = 0;
        double result = Integer.MAX_VALUE;
        for(int i = 0; i < quality.length; i++) {
            workers[i][0] = (double) wage[i] / (double) quality[i];
            workers[i][1] = quality[i];
        }
        Arrays.sort(workers, (o1, o2) -> {
            if(o1[0] - o2[0] == 0) return 0;
            if(o1[0] - o2[0] > 0) return 1;
            return -1;
        });
        for(double[] worker : workers) {
            if(heap.size() == K) {
                sum -= heap.poll();
            }
            heap.add(worker[1]);
            sum += worker[1];
            if(heap.size() == K) {
                result = Math.min(result, sum * worker[0]);
            }
        }
        return result;
    }

  
    public static void main(String args[]) 
    { 
        int n=4;
        int[] quality = { 20, 40, 10, 50};
        int[] wages = {70, 80, 30, 40};
        int k=3;
        System.out.println("The least amount of money needed to form a paid group: "+hireKworkers(quality,wages,k));
    } 
}
The least amount of money needed to form a paid group: 245.0

Complexity Analysis for Minimum Cost to Hire K Workers

Time complexity

O(NlogN) Insertion in heap/priority queue takes logn time and we are traversing the whole array once hence the overall time complexity will be O(NlogN)

Space Complexity

O(N) where N is the size of the input array.

References

Translate »