#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/greedy-algorithms/greedy-optimization/hire-workers-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/greedy-algorithms/greedy-optimization/hire-workers-implementation

Repovive

Hire Workers - Implementation - Greedy Optimization | Greedy Algorithms | Repovive

Repovive.

Greedy Algorithms8 sections · 317 units14h total

Open in Course

Hire Workers - Implementation

The code

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.