589. Hire K for Less
A film crew needs to hire exactly k freelancers from n applicants. Applicant i has a skill score quality[i] and demands a minimum pay of wage[i]. The payroll rules are strict: all hired people are paid in direct proportion to their skill scores (so a person with twice the score gets twice the pay), and nobody may be paid less than their own minimum wage[i]. Pay does not have to be a whole number.
Return the smallest possible total pay for a valid group of exactly k applicants. Answers within 10^-6 of the true value are accepted. The intended solution runs in O(n log n) time and O(n) space.
Example 1
- Input:
- quality = [10,20,5], wage = [70,50,30], k = 2
- Output:
- 105
- Explanation:
Hire the applicants with scores 10 and 5: the pay rate is set by the first one (7 per score point), so they get 70 and 35, totalling 105.
Example 2
- Input:
- quality = [3,1,2], wage = [4,5,3], k = 2
- Output:
- 7.5
- Explanation:
Hiring the applicants with scores 3 and 2 uses a rate of 1.5 per point (set by the second one), so they get 4.5 and 3, totalling 7.5.
Example 3
- Input:
- quality = [3,3,3], wage = [6,9,12], k = 3
- Output:
- 36
- Explanation:
All three must be hired and the highest rate, 4 per point, applies to everyone, so the total is 3 * 3 * 4 = 36.
Constraints
- 1 ≤ k ≤ n ≤ 105, where n = quality.length = wage.length
- 1 ≤ quality[i], wage[i] ≤ 104
How this problem is judged
- Answers
- Numbers are accepted within a tolerance of 1.0E-6: |answer - expected| <= 1.0E-6 x max(1, |expected|).
- Tolerance
0.000001- Time per case
- Python 3,200 msC++ 800 msJava 1,600 msJavaScript 1,600 msTypeScript 1,600 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)