Skip to main content

857. Minimum Cost to Hire K Workers

hardAsked at DoorDash

Hire exactly k workers so that each is paid at least their min-wage AND in proportion to their quality. Minimize total cost. DoorDash uses this for senior backend rounds — the dispatch and pricing problems have the same shape.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in DoorDash loops.

  • Glassdoor (2026-Q1)— DoorDash SWE onsite reports cite this for senior backend rounds tied to dispatch pricing.
  • Blind (2025-12)— DoorDash SDE2 reports note the wage-to-quality ratio sort as the actual interview signal.

Problem

There are n workers. You are given two arrays quality and wage where quality[i] is the quality of the ith worker and wage[i] is the minimum wage expectation for the ith worker. We want to hire exactly k workers to form a paid group. To hire a group of k workers, we must pay them according to the following rules: Every worker in the paid group must be paid at least their minimum-wage expectation. In the group, each worker's pay must be directly proportional to their quality. Given the integer k, return the least amount of money needed to form a paid group satisfying the above conditions. Answers within 10^-5 of the actual answer will be accepted.

Constraints

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

Examples

Example 1

Input
quality = [10,20,5], wage = [70,50,30], k = 2
Output
105.00000

Explanation: Pay 70 to 0-th worker and 35 to 2-th worker.

Example 2

Input
quality = [3,1,10,10,1], wage = [4,8,2,2,7], k = 3
Output
30.66667

Explanation: Pay 4 to 0-th worker, 13.33333 to 2-th and 3-th workers separately.

Approaches

1. Sort by wage/quality ratio + min-quality heap

Sort workers by ratio = wage / quality ascending. For each worker in sorted order, maintain a max-heap of quality (size k). When the heap exceeds k, evict the largest. After k items, group cost = ratio * sum_of_k_smallest_qualities.

Time
O(n log n)
Space
O(n)
function mincostToHireWorkers(quality, wage, k) {
  const workers = [];
  for (let i = 0; i < quality.length; i++) {
    workers.push([wage[i] / quality[i], quality[i]]);
  }
  workers.sort((a, b) => a[0] - b[0]);
  const heap = []; // max-heap on quality
  let qSum = 0;
  let best = Infinity;
  function push(v) {
    heap.push(v);
    let i = heap.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (heap[p] < heap[i]) { [heap[p], heap[i]] = [heap[i], heap[p]]; i = p; }
      else break;
    }
  }
  function pop() {
    const top = heap[0];
    const last = heap.pop();
    if (heap.length) {
      heap[0] = last;
      let i = 0;
      while (true) {
        const l = 2*i+1, r = 2*i+2;
        let big = i;
        if (l < heap.length && heap[l] > heap[big]) big = l;
        if (r < heap.length && heap[r] > heap[big]) big = r;
        if (big === i) break;
        [heap[i], heap[big]] = [heap[big], heap[i]];
        i = big;
      }
    }
    return top;
  }
  for (const [ratio, q] of workers) {
    push(q);
    qSum += q;
    if (heap.length > k) {
      qSum -= pop();
    }
    if (heap.length === k) {
      best = Math.min(best, ratio * qSum);
    }
  }
  return best;
}

Tradeoff: The canonical answer. Two insights: (1) when you fix the highest ratio in the group, that ratio sets everyone's pay rate; (2) given the ratio, you want the k smallest qualities. The max-heap evicts the largest quality.

2. Brute force over all subsets

Enumerate every k-subset; for each, compute the maximum ratio and the total cost. Return the minimum.

Time
O(C(n, k) * k)
Space
O(k)
function mincostBrute(quality, wage, k) {
  const n = quality.length;
  let best = Infinity;
  function recurse(start, picked) {
    if (picked.length === k) {
      let maxRatio = 0;
      let qSum = 0;
      for (const i of picked) {
        maxRatio = Math.max(maxRatio, wage[i] / quality[i]);
        qSum += quality[i];
      }
      best = Math.min(best, maxRatio * qSum);
      return;
    }
    for (let i = start; i < n; i++) {
      picked.push(i);
      recurse(i + 1, picked);
      picked.pop();
    }
  }
  recurse(0, []);
  return best;
}

Tradeoff: Exponential — fails the constraint at n = 10^4. Mention as the obvious approach, then explain why sort+heap wins.

DoorDash-specific tips

DoorDash interviewers grade on whether you derive the RATIO + HEAP insight aloud. State 'in any valid group, the max ratio sets the price for everyone; given that ratio I want the k smallest qualities' BEFORE coding. That's the actual interview signal.

Common mistakes

  • Confusing the direction of the heap — you want to evict the LARGEST quality (because larger quality multiplies the ratio).
  • Forgetting to check heap.length === k before updating best (don't bias to partial groups).
  • Off-by-one when popping the heap after pushing.

Follow-up questions

An interviewer at DoorDash may pivot to one of these next:

  • Profitable Schemes (LC 879) — DP-based group selection.
  • Maximum Performance of a Team (LC 1383) — same structure: sort + heap.
  • Minimum Cost to Connect Sticks (LC 1167) — min-heap greedy.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why sort by wage/quality?

Because the worker with the highest ratio in your group SETS the rate for everyone. By processing workers in increasing ratio order and trying each as the 'rate-setter,' we cover every meaningful group.

Why a MAX-heap on quality, not min?

We want the k SMALLEST qualities to minimize total cost = rate * sum_qualities. A max-heap of size k naturally evicts the worst (largest).

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Minimum Cost to Hire K Workers and other DoorDash interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →