Explanation: We pay 4 to 0th worker, 13.33333 to 2nd and 3rd workers separately.

Solution

Method 1 - Using quality to wage ratio and Priority Queue

This problem can also be thought of as if we are going in market, and buying different baskets of bananas OR apples. Now, the example looks like:

min-cost-to-hire-k-workers-banana-analogy.excalidraw

Now, the rule is, when we buy k baskets, we have to pay the highest unit price for all bananas.

For e.g. - if we buy 20 bananas of ₹2.5/unit and 10 bananas of ₹7/unit together, we have to pay the highest ₹7/unit for all of them (20 + 10) * ₹7/unit

We want k baskets, we try the cheapest bananas first i.e. cheapest in terms of unit price.

So, we start with ₹2.5/unit (buy 20 units) ⇨ It costed us 50.
Add another basket, try the next higher unit price is ₹6/unit (buy 5 units). Now all bananas are ₹6/unit (20 + 5) ⇨ It costed us ₹150. Now, we have touched target of k baskets. But, we still need to process more baskets, so which basket should we remove from selection?
The next unit price to try will be higher ₹7/unit.
1. If we need to remove one basket, they have the same unit price, we remove the ones with more units or quantity i.e. the 20 one. Now, we have ₹6/unit (for 5 unit).
2. Now, all bananas are at ₹7/unit (10 + 5) ⇨ Now, the cost is 105

Cheaper unit price will never be used again, so removing the baskets with highest number of bananas i.e. quantity is always safe.

Algorithm

We have 2 requirements:

Every worker in the paid group must be paid at least their minimum wage expectation.
In the group, each worker's pay must be directly proportional to their quality. This means if a worker’s quality is double that of another worker in the group, then they must be paid twice as much as the other worker.

Now, lets jump to algorithm

Sort the input arrays based on the unit price aka $W_i / Q_i$, where $W_i$ is wage of ith worker and $Q_i$ is quality. (We sort because to suite requirement 2). Lets call it

Related Tags