Minimum Cost to Hire K Workers (Leetcode)

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⁵of the actual answer will be accepted.

Before jumping to any conclusion let’s first break down the question
Further breaking down lets suppose you are given 2 workers

quality = [10, 20]
wages = [70, 50]

and we have to select only 1 worker with minimum wage then our answer will be 1st index worker obviously

now we add another worker with quality = 5 and wage = 30

quality = [10, 20, 5]
wages = [70, 50, 30]

Now how we are going to choose

lets see the choosing criteria one more time and keep focus on this line

“Every worker in the paid group should be paid in the ratio of their quality compared to other workers in the paid group.”

so who will decide what amount to pay to each customer

lets see by example

lets suppose we have chosen 2 worker

quality = [10,20]
wage = [70,50]

is 1st index worker decide which what wage to choose pay?

if 1st index worker decides it’s wage to quality ration will say that for 1 quality of work 2.5 wage is to be paid now you cannot pay for 0 index worker because it needs 7 wage for 1 quality of work
then 0 index worker can decide?
Yes because this worker is giving 7 wage for 1 quality of work s you can see those who have wage to quality ratio more will decide what amount to be paid to each customer.

now 1st part done who will decide

now 2nd part what array to choose

so that we get minimum amount now this question comes to like you have n elements and you have to choose k smallest elements in them if you have gone through this type of question then you know a max_heap will work if you haven’t practiced this type of question I strongly recommend this question will paste the link below.

Intuition

1. store the quality and wage in a array kind of 2d array [[wage[i],quality[i]],[wage[j],quality[j]]]
2. sort the array based on wage/quality ratio
3. then at index “i” select k smallest qualities in this the ith worker will decide what amount to pay
4. answer for ith index is ((sum of k smallest quality till index I)*(wage[i]/quality[i]));
5. iterate for every index and get minimum answer

class Solution {
public:
    static bool comp(pair<int,int> a,pair<int,int> b)
    {
        if(a.second*b.first <= b.second*a.first)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) {
        vector<pair<double,double>> vec;
        for(int i=0;i<quality.size();i++)
        {
            vec.push_back({quality[i],wage[i]});
        }
        
        sort(vec.begin(),vec.end(), comp);
        priority_queue<double> pq;
        double curr=0;
        vector<double> best_q;
        
        for(int i=0;i<vec.size();i++)
        {
            pq.push(vec[i].first);
            curr+=vec[i].first;
            if(pq.size()>k)
            {
                curr-=pq.top();
                pq.pop();
            }
            best_q.push_back(curr);
        }
        double ans = INT_MAX;
        
        for(int i=k-1;i<best_q.size();i++)
        {
            ans = min(ans, best_q[i]*(vec[i].second/vec[i].first));
        }
        
        return ans;
    }
};

Link for this problem — https://leetcode.com/problems/minimum-cost-to-hire-k-workers/

Link for Kth Largest Element in Array — https://leetcode.com/problems/kth-largest-element-in-an-array/