HardArrayGreedySortingHeapUpdated Sep 2026

857. Minimum Cost to Hire K Workers

Asked at Apple

Difficulty

Hard

Time

O(n log n)

Space

O(n)

Pattern

Array

Companies

1

Problem

You are given two integer arrays, quality and wage, both of length n. Worker i has quality quality[i] and expects to be paid at least wage[i]. You must hire exactly k workers.

Two rules apply to the group you hire. First, every hired worker must get at least their own wage[i]. Second, pay must be proportional to quality: if one worker's quality is twice another's, their pay must be exactly twice as much. So once you fix a pay rate r (dollars per unit of quality), every hired worker i earns r * quality[i].

Return the smallest total cost of a valid group of k workers. A group is valid if there is some rate r such that r * quality[i] >= wage[i] for every hired worker. Answers within 10^-5 of the true value are accepted.

One rate for the whole group

quality10205012Worker 0 has quality 10, worker 1 has 20, worker 2 has5.wage705030012We hire workers 0 and 2 (k = 2). Their needed ratesare 7 and 6.rate = max(70/10, 30/5) = 7cost = 7 * (10 + 5) = 105
Every hired worker is paid the same rate times their quality, and that rate must cover the strictest worker's expectation.

Constraints

  • ●n == quality.length == wage.length
  • ●1 <= k <= n <= 10^4
  • ●1 <= quality[i], wage[i] <= 10^4

Examples

Example 1
Inputquality = [10,20,5], wage = [70,50,30], k = 2
Output105.00000
WhyHire workers 0 and 2. Worker 0 needs rate at least 70/10 = 7, worker 2 needs at least 30/5 = 6. The binding rate is 7, so pay is 7*10 = 70 and 7*5 = 35. Total = 105. Any other pair costs more.
Example 2
Inputquality = [3,1,10,10,1], wage = [4,8,2,2,7], k = 3
Output30.66667
WhyHire workers 0, 2 and 3. Their required rates are 4/3, 2/10 and 2/10, so the binding rate is 4/3. Pay = 4/3 * (3 + 10 + 10) = 4/3 * 23 = 30.66667.

Asked At

1 companies
CompanyDifficulty
AppleHardView all Apple questions →

How to Think About It

1

Compute the wage-to-quality ratio for each worker and sort by this ratio

2

Iterate through workers sorted by ratio, treating each as the ratio-defining worker

3

Maintain a max-heap of K-1 qualities from previously seen workers

4

For each worker, the cost is the sum of K-1 largest qualities times the current ratio

5

Track the minimum cost across all possible ratio-defining workers

Optimal Approach

Sort workers by their wage-to-quality ratio. For each worker i (in sorted order), assume worker i defines the group ratio (all workers are paid at quality[i] * ratio_i). To minimize cost with this ratio, pick K-1 workers from among those with ratio <= ratio_i who have the smallest qualities. Use a max-heap to maintain the K-1 smallest qualities. When the heap reaches size K-1, the cost is (sum of heap + quality[i]) * ratio_i. Track the minimum cost. The key insight is that the highest-ratio worker in any group determines the pay rate.

Sort by ratio, keep the k smallest qualities

sorted by wage/quality6:q57:q102.5:q20012Workers sorted by ratio: (6, q=5), (7, q=10), (2.5,q=20) — here shown as ratio:quality labels.max-heap of qualities510frontbackAfter processing the first two workers, the heap holdsthe k = 2 smallest qualities seen so far.cost = (sum of k qualities) * current ratioanswer = min over all workers
The worker with the highest ratio in the group sets the rate, so we try each worker as that ratio-setter and greedily keep the cheapest qualities.
ComplexityTime O(n log n)Space O(n)Sorting the workers costs O(n log n); the heap holds at most k qualities, so each push/pop is O(log k).

What Trips People Up in Real Interviews

1

Clarify that pay is proportional: paid[i] = quality[i] * ratio

2

Explain that the worker with the highest ratio determines the group ratio

3

Mention why sorting by ratio and using a max-heap gives the optimal solution

4

Discuss that the heap maintains the K-1 workers with smallest quality from previous groups

5

State the time complexity is O(N log N) for sorting and O(N log K) for heap operations

Solution Code

O(n log n) time
import heapq

class Solution:
    def mincostToHireWorkers(self, quality: list[int], wage: list[int], k: int) -> float:
        workers = sorted([(w / q, q) for q, w in zip(quality, wage)])
        result = float('inf')
        total_quality = 0
        max_heap = []

        for ratio, q in workers:
            total_quality += q
            heapq.heappush(max_heap, -q)

            if len(max_heap) > k:
                total_quality += heapq.heappop(max_heap)

            if len(max_heap) == k:
                result = min(result, total_quality * ratio)

        return result

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Minimum Cost to Hire K Workers problem?

Given N workers with quality and minimum wage expectations, hire exactly K workers such that the total cost is minimized. Each hired worker must be paid proportionally based on their quality-to-wage ratio. This problem combines greedy sorting with heap-based optimization.

How do you solve Minimum Cost to Hire K Workers?

The optimal approach runs in O(n log n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Minimum Cost to Hire K Workers?

Minimum Cost to Hire K Workers is asked at Apple. It is a hard difficulty problem.

What are common mistakes on Minimum Cost to Hire K Workers?
  • Clarify that pay is proportional: paid[i] = quality[i] * ratio
  • Explain that the worker with the highest ratio determines the group ratio
  • Mention why sorting by ratio and using a max-heap gives the optimal solution
  • Discuss that the heap maintains the K-1 workers with smallest quality from previous groups
  • State the time complexity is O(N log N) for sorting and O(N log K) for heap operations