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

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

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

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

done