The problem
Each worker has a quality and minimum wage expectation. Pay must be proportional to quality within the hired group, and everyone gets at least their minimum. Hire exactly k workers at minimum total cost.
Stuck? Reveal hints one at a time
How to approach it
- 1Compute ratio = wage / quality per worker; sort ascending by ratio.
- 2Sweep workers as the "captain" whose ratio prices the group.
- 3Maintain a max-heap of qualities and a running quality sum of at most k workers with the smallest qualities so far.
- 4When the pool holds k workers, candidate cost = qualitySum × captain’s ratio; take the minimum over all captains.
Key insight
Sorting by ratio makes the current worker’s ratio the binding one for everyone already seen — reducing the problem to "maintain the k smallest qualities", a bounded max-heap job.
The solution
Watch out for
- Evict the LARGEST quality when over k — you are minimizing the quality sum.
- Floating-point ratios are fine here, but sort stability with exact fractions (wage·q2 vs wage·q1) is the airtight version.