# Minimum Cost to Hire K Workers

There are n workers. The i-th worker has a quality[i] and a minimum wage expectation wage[i].

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

So for any two workers in the paid group,

we have wage[i] : wage[j] = quality[i] : quality[j]

So we have wage[i] : quality[i] = wage[j] : quality[j]=x

We pay the wage to every worker in the group with the same ratio compared to his quality.

total cost = x* sum of the quality of k workers;

**2. Every worker in the paid group must be paid at least their minimum-wage expectation.”**

For every worker, he has an expected ratio of wage compared to his quality. if someone gets paid more than equal to its expected ratio of wage. constraint satisfied

**Brute Force :**

- pick one worker and calculate his expected ratio of wage and try to find k workers having expected ratio of a wage less than or equal to pick one.
- keep tracking the total cost

here observation, for the picked worker, **parameters are [ set of qualities, set of expectation wage, paid wage ratio] and the answer is k minimum qualities having wage ratio less than or equal to paid wage ratio.**problem is similar to find k minimum elements bounded by some parameter.

if we redefine the brute force Approach

- let’s arrange workers in the order of the expected ratio of wage.
- pick one worker and find so far k minimum qualities (max-heap can be used here)
- and keep track of the answer

done