527. Minimum Cost to Hire K Workers
You are staffing a project and must hire exactly k of the n candidates. Candidate i has a skill rating quality[i] and a minimum acceptable pay wage[i].
The group you hire must be paid under two rules:
- Proportional pay: within the group, pay scales with quality — a worker with twice the quality of a teammate must earn exactly twice as much.
- Minimum wage: every hired worker must receive at least their own
wage[i].
Return the minimum total amount of money needed to hire a valid group of k workers. The optimum may not be an integer: print it rounded to exactly 5 digits after the decimal point (e.g. 30.66667).
Example 1:
Input: quality = [10, 20, 5], wage = [70, 50, 30], k = 2
Output: 105.00000
Explanation: Hire workers 0 and 2 at a rate of 7 dollars per quality point: worker 0 gets 70 (exactly their minimum) and worker 2 gets 35 (above their minimum of 30). Total 105 — no other pair is cheaper.
Example 2:
Input: quality = [3, 1, 10, 10, 1], wage = [4, 8, 2, 2, 7], k = 3
Output: 30.66667
Explanation: Hire workers 0, 2 and 3 at a rate of 4/3 per quality point: they receive 4, 13.33333 and 13.33333. Worker 0 is paid exactly their minimum and the two big workers clear theirs easily.
Constraints:
- 1 ≤ k ≤ n ≤ 10⁴
- quality.length == wage.length == n
- 1 ≤ quality[i], wage[i] ≤ 10⁴
- The answer is the exact optimum rounded to 5 decimal places.
Hints:
Proportional pay means the whole group shares one pay rate r = dollars per quality point: worker i receives r * quality[i]. The minimum-wage rule forces r >= wage[i] / quality[i] for every hired worker, so the cheapest feasible rate for a group is the maximum ratio wage[i] / quality[i] inside it.
Flip the search: instead of choosing a group and deriving its rate, choose the rate-setter. If worker i has the largest ratio in the group, the total cost is (wage[i] / quality[i]) * (sum of the group's qualities) — so among all workers whose ratio is <= worker i's, you want the k smallest qualities.
Sort workers by ratio and sweep. Maintain the k smallest qualities seen so far with a max-heap and a running quality sum; when the heap holds k workers, the current worker's ratio times the sum is one candidate cost. The best candidate over the sweep is the answer.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: quality = [10, 20, 5], wage = [70, 50, 30], k = 2
Expected output: 105.00000