Total Cost to Hire K Workers

Problem in plain words

Workers stand in a line, each with a hiring cost. You run k hiring rounds. In each round you only look at the first candidates workers and the last candidates workers still in line (if those groups overlap, it is just everyone left). You hire the cheapest one among them; on a tie, the one with the smaller index wins. The hired worker leaves the line. Return the total cost of all k hires.

Example: costs = [6, 3, 8, 1, 5, 2], k = 3, candidates = 2. Round 1 sees 6, 3 and 5, 2 → hire 2. Round 2 sees 6, 3 and 1, 5 → hire 1. Round 3 sees 6, 3 and 8, 5 → hire 3. Total 6.

Intuition

Each round asks for the minimum of two small windows, and after a hire the window that lost a worker gains the next worker from the middle. Two min-heaps model the windows: left holds the front candidates and right the back ones. Pointers i and j mark the next unseen worker from each end, and i <= j guarantees nobody is placed in both heaps. On a tie between the two heap tops, pick left, since every front index is smaller than every back index.

Approach

1. Set i = 0, j = n - 1, and create two empty min-heaps.
2. At the start of each round, top up left from i (moving right) and right from j (moving left) until each holds candidates workers or i > j.
3. Compare the tops. If right is non-empty and (left is empty or right's top is strictly smaller), hire from right; otherwise hire from left.
4. Add the cost to the total and repeat for k rounds.

Dry run

costs = [6, 3, 8, 1, 5, 2], k = 3, candidates = 2.

Java solution

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

Python solution

class Solution:
    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:
        left, right = [], []
        i, j = 0, len(costs) - 1
        total = 0
        for _ in range(k):
            while len(left) < candidates and i <= j:
                heapq.heappush(left, costs[i])
                i += 1
            while len(right) < candidates and i <= j:
                heapq.heappush(right, costs[j])
                j -= 1
            if right and (not left or right[0] < left[0]):
                total += heapq.heappop(right)
            else:
                total += heapq.heappop(left)
        return total

Complexity

Edge cases and common mistakes

• Overlapping windows — when 2 · candidates >= n, the i <= j check stops the second heap from re-adding workers already in the first.
• Tie-breaking — on equal costs, the front worker has the smaller index, so take from left (use strict < for right).
• One heap runs empty — late in the process all remaining workers may sit in one heap; guard the comparison against empty heaps.
• Overflow — k · max cost can reach 10^10, so return a long in Java.