Cheapest 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;
}

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