Total Cost to Hire K Workers

hard heap greedy two pointers

Problem

You're hiring k workers from a row of candidates. In each session you may hire only from a window of size candidates at the front and back of the still-unhired row. Always hire the cheapest available worker (ties broken by lower index). Use two min-heaps — one for the front window, one for the back — and two pointers that converge.

Inputcosts = [17,12,10,2,7,2,11,20,8], k = 3, candidates = 4

Output11

Hire 2, then 2, then 7 from the rolling windows.

costs (comma-separated)

candidates

import heapq
def total_cost(costs, k, m):
    l, r = 0, len(costs) - 1
    left, right = [], []
    while len(left) < m and l <= r:
        heapq.heappush(left, costs[l]); l += 1
    while len(right) < m and l <= r:
        heapq.heappush(right, costs[r]); r -= 1
    total = 0
    for _ in range(k):
        if not right or (left and left[0] <= right[0]):
            total += heapq.heappop(left)
            if l <= r: heapq.heappush(left, costs[l]); l += 1
        else:
            total += heapq.heappop(right)
            if l <= r: heapq.heappush(right, costs[r]); r -= 1
    return total

function totalCost(costs, k, m) {
  let l = 0, r = costs.length - 1;
  const left = [], right = [];
  while (left.length < m && l <= r) { left.push(costs[l++]); }
  while (right.length < m && l <= r) { right.push(costs[r--]); }
  left.sort((a, b) => a - b); right.sort((a, b) => a - b);
  let total = 0;
  for (let i = 0; i < k; i++) {
    if (right.length === 0 || (left.length && left[0] <= right[0])) {
      total += left.shift();
      if (l <= r) { left.push(costs[l++]); left.sort((a, b) => a - b); }
    } else {
      total += right.shift();
      if (l <= r) { right.push(costs[r--]); right.sort((a, b) => a - b); }
    }
  }
  return total;
}

class Solution {
    public long totalCost(int[] costs, int k, int m) {
        int l = 0, r = costs.length - 1;
        PriorityQueue<Integer> left = new PriorityQueue<>(), right = new PriorityQueue<>();
        while (left.size() < m && l <= r) left.offer(costs[l++]);
        while (right.size() < m && l <= r) right.offer(costs[r--]);
        long total = 0;
        for (int i = 0; i < k; i++) {
            if (right.isEmpty() || (!left.isEmpty() && left.peek() <= right.peek())) {
                total += left.poll();
                if (l <= r) left.offer(costs[l++]);
            } else {
                total += right.poll();
                if (l <= r) right.offer(costs[r--]);
            }
        }
        return total;
    }
}

long long totalCost(vector<int>& costs, int k, int m) {
    int l = 0, r = (int)costs.size() - 1;
    priority_queue<int, vector<int>, greater<int>> left, right;
    while ((int)left.size() < m && l <= r) left.push(costs[l++]);
    while ((int)right.size() < m && l <= r) right.push(costs[r--]);
    long long total = 0;
    for (int i = 0; i < k; i++) {
        if (right.empty() || (!left.empty() && left.top() <= right.top())) {
            total += left.top(); left.pop();
            if (l <= r) left.push(costs[l++]);
        } else {
            total += right.top(); right.pop();
            if (l <= r) right.push(costs[r--]);
        }
    }
    return total;
}

Explanation

You always want to hire the cheapest worker available, but only from the candidates workers at the very front or the very back of the row. The clever part is keeping two small min-heaps so the cheapest of each window is always one peek away.

We seed a left heap with the first m costs and a right heap with the last m costs, using two pointers l and r that move inward as workers get pulled in. Each round, we compare the tops of both heaps and hire the smaller one (ties go to the left side, which means the lower index).

After hiring, we refill the side we took from with the next still-unhired cost (if any are left between l and r). This keeps each window at size m until the middle runs out.

Example: costs = [17,12,10,2,7,2,11,20,8], k = 3, candidates = 4. The left window is {17,12,10,2} and the right is {8,20,11,2}. We hire 2, then another 2, then 7, giving total 11.

Because each hire only does a couple of heap operations, the work stays small even for long rows.

Time: O((k + m) log m) Space: O(m)