There are n workers. Each worker has a quality and a minimum wage expectation. To hire exactly k workers, every hired worker must be paid in proportion to quality, and each worker must receive at least their minimum wage. Return the minimum total cost. Pattern focus: Exchange Argument. Sort workers by wage-to-quality ratio and maintain the best k qualities using a max-heap so that the current ratio becomes the team’s payment rate.
quality = worker quality, wage = minimum wage, k = number of workers to hire
minimum total hiring cost as a decimal number
Example 1:
Input:
quality = [10,20,5] wage = [70,50,30] k = 2
Output:
105.0
Explanation:
The minimum cost is achieved by hiring workers 0 and 2 with a common ratio of 7.
Example 2:
Input:
quality = [3,1,10,10,1] wage = [4,8,2,2,7] k = 3
Output:
30.666666666666668
Explanation:
The classic optimal selection yields a total cost of approximately 30.6666667.
Example 3:
Input:
quality = [1,1,1] wage = [1,1,1] k = 2
Output:
2.0
Explanation:
When all ratios are equal, the total cost is simply the sum of the selected qualities times that ratio.