Minimum Cost to Hire K Workers - Video Solutions

Problem Overview: You are given two arrays: quality and wage. Each worker has a minimum wage expectation and a work quality. When hiring a group of k workers, everyone must be paid using the same wage-to-quality ratio, and each worker must receive at least their minimum wage. The goal is to choose k workers with the smallest possible total cost.

Approach 1: Sorting-Based Greedy Scan (O(n^2 log n) time, O(n) space)

The key constraint is that if a worker with ratio wage[i] / quality[i] sets the payment rate, every other worker must be paid using at least that ratio. Start by computing this ratio for every worker and sorting workers by it using sorting. Treat each worker as the "captain" who defines the group ratio. For that ratio, you want the k workers with the smallest total quality among all workers seen so far, because total cost equals ratio * sum(quality). A simple but slower method repeatedly collects candidate qualities and sorts them to pick the smallest k. This works conceptually but becomes inefficient as the candidate set grows.

Approach 2: Greedy + Max Heap (O(n log n) time, O(n) space)

The optimal solution improves the previous idea by maintaining the k smallest qualities dynamically. First compute each worker’s ratio and sort workers by ratio ascending. Iterate through the sorted list and keep a running group of workers. Track the sum of qualities and store qualities inside a max heap using a heap (priority queue). If the heap grows larger than k, remove the worker with the largest quality because that worker contributes the most to the cost. When the heap size reaches exactly k, compute the total cost as current_ratio * quality_sum. Since ratios increase as you iterate, each step evaluates the cheapest possible group whose highest ratio is the current worker. This greedy choice ensures the minimum cost.

The algorithm works because the payment ratio must match the highest ratio in the chosen group. Sorting guarantees that once a worker defines the ratio, all earlier workers already satisfy it. The heap keeps the quality sum minimal, which directly minimizes total payment.

Recommended for interviews: The greedy + max heap approach is the expected solution. It combines greedy reasoning with efficient data structures and runs in O(n log n). Interviewers often accept the conceptual greedy explanation first, then expect the heap optimization to maintain the smallest k qualities efficiently.