#2462 - Total Cost to Hire K Workers

MediumHeap / Priority Queue

You are given a 0-indexed integer array costs where costs[i] is the cost of hiring the i-th worker. You are also given two integers k and candidates. In each hiring round, choose the worker with the lowest cost from either the first candidates workers or the last candidates workers (remove them from the pool). Hire exactly k workers. Return the total cost.

Input	Output
costs = [17,12,10,2,7,2,11,20,8], k = 3, candidates = 4	11
costs = [1,2,4,1], k = 3, candidates = 3	4

Solution Space

Try it

/**
 * Returns the total cost of hiring k workers, picking the cheapest
 * from the first or last `candidates` workers each round.
 *
 * Uses two min-heaps (left and right candidate pools) and two
 * pointers to track the boundary of unassigned workers.
 *
 * @param costs      Array of worker costs
 * @param k          Number of workers to hire
 * @param candidates Pool size from each end
 * @returns          Minimum total hiring cost
 */
export function totalCost(
  costs: number[],
  k: number,
  candidates: number,
): number {
  const n = costs.length;
  const left: number[] = []; // min-heap for left pool
  const right: number[] = []; // min-heap for right pool
  let lo = 0;
  let hi = n - 1;

  // Seed both heaps with initial candidates
  while (lo < candidates && lo <= hi) left.push(costs[lo++]);
  while (hi >= n - candidates && hi >= lo) right.push(costs[hi--]);

  left.sort((a, b) => a - b);
  right.sort((a, b) => a - b);

  let total = 0;

  for (let i = 0; i < k; i++) {
    const lMin = left.length > 0 ? left[0] : Infinity;
    const rMin = right.length > 0 ? right[0] : Infinity;

    if (lMin <= rMin) {
      total += left.shift()!;
      if (lo <= hi) {
        insertSorted(left, costs[lo++]);
      }
    } else {
      total += right.shift()!;
      if (lo <= hi) {
        insertSorted(right, costs[hi--]);
      }
    }
  }

  return total;
}

function insertSorted(arr: number[], val: number): void {
  let i = arr.length;
  arr.push(val);
  while (i > 0 && arr[i - 1] > val) {
    arr[i] = arr[i - 1];
    i--;
  }
  arr[i] = val;
}

Approach: two min-heaps – maintain a left heap (first `candidates` workers) and a right heap (last `candidates` workers). Each round, pick the cheaper top, then refill from the middle.

Time: O((k + candidates) · log candidates) with a proper heap.

Space: O(candidates) – both heaps combined.

#2336 Smallest Number in Infinite Set

#2542 Maximum Subsequence Score