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:

- 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.

## 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.