Total Cost to Hire K Workers — Solution

Problem

You have n workers, each with a hiring cost. You need to hire exactly k of them in k sessions. In each session, you pick the cheapest worker among the first candidates and last candidates still-available workers, breaking ties in favor of the leftmost worker. Return the total cost.

• Input: costs = [17,12,10,2,7,2,11,20,8], k = 3, candidates = 4
• Output: 11
• Explanation: Session 1 hires index 3 (cost 2), session 2 hires index 5 (cost 2), session 3 hires index 4 (cost 7); total = 11.

Intuition

Think of the available workers as two sliding windows — the leftmost candidates and rightmost candidates un-hired workers. Each session you need the minimum of those two windows. Rescanning both windows is O(candidates) per round; a min-heap for each window replaces that with O(log candidates) and after each hire you fill the gap by pulling in the next inward worker.

Approach 1 — Linear Scan

For each of k sessions, scan the first candidates and last candidates un-hired workers, find the minimum, then mark that worker hired. A boolean array tracks who's been hired; the right-side scan uses strict < so the left side wins ties.

1. Allocate a hired array of size n, initialized to false.
2. For each session, do a forward pass to find the best among the first candidates un-hired workers.
3. Do a reverse pass for the last candidates un-hired workers, updating the best only on strict improvement.
4. Mark the chosen worker hired and accumulate their cost.

1def totalCost(costs: list[int], k: int, candidates: int) -> int:
2    n = len(costs)
3    hired = [False] * n
4    total = 0
5
6    for _ in range(k):
7        best_cost, best_idx = float('inf'), -1
8
9        # Find the minimum among the first `candidates` un-hired workers
10        left_seen = 0
11        for i in range(n):
12            if not hired[i]:
13                if costs[i] < best_cost:
14                    best_cost, best_idx = costs[i], i
15                left_seen += 1
16                if left_seen == candidates:
17                    break
18
19        # Strict < so the left side wins when both sides have equal cost
20        right_seen = 0
21        for i in range(n - 1, -1, -1):
22            if not hired[i]:
23                if costs[i] < best_cost:
24                    best_cost, best_idx = costs[i], i
25                right_seen += 1
26                if right_seen == candidates:
27                    break
28
29        hired[best_idx] = True
30        total += best_cost
31
32    return total

Time: O(k × n) — each of the k sessions may scan up to n elements to locate candidates un-hired workers.
Space: O(n) — the boolean hired array.

Approach 2 — Two Min-Heaps

Keep a min-heap for the left window and another for the right window, each seeded with candidates elements. Two index pointers lo and hi track the interior boundary. After each hire, pull the next inward worker into the vacated heap (if lo ≤ hi) to keep both windows full.

1. Push costs[0..candidates-1] into left_heap, advancing lo.
2. Push costs[n-1] down to costs[n-candidates] into right_heap, decrementing hi; stop early if lo > hi to prevent overlap.
3. For each session, compare the heap tops — pick left on a tie to satisfy the leftmost-index rule.
4. After popping, push the next interior worker into the same heap and advance that pointer, but only if lo ≤ hi.

1import heapq
2
3def totalCost(costs: list[int], k: int, candidates: int) -> int:
4    n = len(costs)
5    lo, hi = 0, n - 1
6    left_heap: list[int] = []
7    right_heap: list[int] = []
8
9    # Seed the left window; lo marks the next index to offer to the left heap
10    for _ in range(candidates):
11        if lo <= hi:
12            heapq.heappush(left_heap, costs[lo])
13            lo += 1
14
15    # Seed the right window; lo <= hi guard prevents overlap with the left window
16    for _ in range(candidates):
17        if lo <= hi:
18            heapq.heappush(right_heap, costs[hi])
19            hi -= 1
20
21    total = 0
22    for _ in range(k):
23        left_min = left_heap[0] if left_heap else float('inf')
24        right_min = right_heap[0] if right_heap else float('inf')
25
26        if left_min <= right_min:  # <= so left heap wins on equal cost
27            total += heapq.heappop(left_heap)
28            if lo <= hi:  # refill the left window with the next interior worker
29                heapq.heappush(left_heap, costs[lo])
30                lo += 1
31        else:
32            total += heapq.heappop(right_heap)
33            if lo <= hi:  # refill the right window with the next interior worker
34                heapq.heappush(right_heap, costs[hi])
35                hi -= 1
36
37    return total

Time: O((k + candidates) × log candidates) — O(candidates log candidates) to seed both heaps, then O(log candidates) per session for k sessions.
Space: O(candidates) — each heap holds at most candidates elements at any time.

Complexity Summary

Common Mistakes

• Omitting the lo ≤ hi guard during right-heap initialization — when 2 × candidates ≥ n, the two windows overlap. Without the guard, the same worker enters both heaps and can be "hired" twice, producing an answer that is too small.
• Using < instead of ≤ when comparing heap tops — the problem requires the left side to win on ties. leftMin <= rightMin picks left on equal cost; flipping to < silently breaks this rule on inputs with duplicate costs.
• Using a 32-bit integer for the total — k can be up to 10⁵ and each cost up to 10⁵, so the total can reach 10¹⁰, which overflows a 32-bit signed integer. Use long in Java or long long in C++.
• Advancing the wrong pointer after a pop — after popping from left_heap, you refill from lo (then increment lo); after popping from right_heap, you refill from hi (then decrement hi). Swapping them corrupts both windows.
• Using ≤ in the brute-force right-side comparison — this lets the right side steal a hire on ties, violating the leftmost-index rule and producing a wrong answer when equal costs appear in both windows.

Related Problems

• Merge K Sorted Lists — heap used to efficiently extract the minimum from k sorted sequences each step
• Kth Largest Element in an Array — heap for k-selection without fully sorting the array
• Furthest Building You Can Reach — min-heap greedy that keeps the k most valuable allocations seen so far
• Find K Closest Elements — maintaining a sliding window of k candidates with heap-based ordering
• K Closest Points to Origin — heap to select k elements by a custom cost criterion