Description
Hire k workers with minimum cost. Each worker paid proportionally to their quality, at least their wage.
Examples
Input:
quality = [10,20,5], wage = [70,50,30], k = 2Output:
105.0Explanation:
Hire workers 0 and 2.
Input:
quality = [1], wage = [1], k = 2Output:
105.0Explanation:
Edge case with a single-element array.
Input:
quality = [3,1,10,10,1], wage = [4,8,2,2,7], k = 3Output:
30.666666666666668Explanation:
Three workers must be hired. The optimal group is workers 0, 2, and 3 (qualities [3,10,10], wages [4,2,2]). The highest wage-to-quality ratio is 4/3, so all workers are paid proportionally. Total cost is minimized at this ratio.
Constraints
- •
1 ≤ k ≤ quality.length ≤ 10⁴