Wage Group Cost
Problem
A contractor must hire exactly k workers for a job. Worker i has a work quality quality[i] and a minimum acceptable pay minWage[i]. Within the hired group, pay must be proportional to quality (all workers get the same pay per unit of quality), and every hired worker must receive at least their minimum.
Return the minimum total pay for a valid group of k workers.
Example 1
- Input:
- quality = [10, 20, 5], minWage = [70, 50, 30], k = 2
- Output:
- 105.0
Hire workers 0 and 2. Worker 0 needs 7 per quality unit, worker 2 needs 6; paying 7 per unit gives 70 and 35, total 105.
Example 2
- Input:
- quality = [3, 1, 10, 10, 1], minWage = [4, 8, 2, 2, 7], k = 3
- Output:
- 30.66667
Hire workers 0, 2 and 3 at 4/3 per unit: 4 + 13.333 + 13.333 ≈ 30.667.
Constraints
- 1 ≤ k ≤ n ≤ 10^4
- 1 ≤ quality[i], minWage[i] ≤ 10^4
- Answers within 10^-5 are accepted.
Hint
Show the first hint
In a fixed group, what pay rate per unit of quality is forced on you?
Walkthrough
How to approach it
01Clarify before coding
- Exactly k workers? Yes.
- Is pay continuous (fractions allowed)? Yes, the answer is a float.
- Does 'proportional to quality' mean one common rate per unit of quality? Yes.
02Brute force
Try every group of k workers; its cost is max(minWage/quality) × sum(quality). Keep the minimum.
Cost: C(n, k) groups: exponential. Fixing the rate-setting worker and choosing the k - 1 smallest qualities by sorting each time is O(n² log n).
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.