Hire Workers - Implementation

function mincostToHireWorkers(quality, wage, k)
 workers := list of (wage[i]/quality[i], quality[i])
 sort workers by ratio ascending
 heap := max-heap of qualities
 qualitySum := 0
 minCost := infinity
 for each (ratio, q) in workers
 heap.push(q)
 qualitySum := qualitySum + q
 if heap.size() > k then
 qualitySum := qualitySum - heap.pop()
 if heap.size() = k then
 minCost := min(minCost, ratio * qualitySum)
 return minCost

$O(n \log n)$ time, $O(n)$ space.

Process workers in ratio order, maintaining the $k$ smallest quality workers. Each worker becomes the potential captain.