LeetCode 2462 - Total Cost to Hire K Workers

LeetCode Problem 2462

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Heap (Priority Queue), Simulation

Solution

Problem Understanding

The problem asks us to simulate a process of hiring k workers from a list costs, where each worker has an associated cost. We can hire workers only from the first candidates workers or the last candidates workers in each hiring session. The goal is to compute the total cost incurred after hiring exactly k workers, always choosing the worker with the minimum cost from the allowed candidates. If multiple workers have the same cost, the one with the smallest index is selected. Once a worker is hired, they are removed from consideration.

The input consists of an integer array costs of length up to 10^5, which implies that any algorithm must be efficient, ideally O(n log n) or better. The integers k and candidates specify the number of workers to hire and the size of the pool from both ends, respectively. The output is a single integer, the sum of the costs of the k hired workers.

Edge cases include situations where candidates is greater than or equal to half the array length, arrays where all elements are the same, and arrays of minimum length. These require careful handling of overlapping candidate pools and tie-breaking by index.

Approaches

The brute-force approach is to repeatedly scan the first candidates and last candidates workers to find the lowest cost worker, remove them, and accumulate the total cost. This would take O(k * candidates) per selection, which could reach O(k * n) in the worst case. For large n and k, this is inefficient.

The optimal approach uses two min-heaps (priority queues) to maintain the smallest cost candidates from both ends of the array. We initially push the first candidates workers into a left heap and the last candidates workers into a right heap. During each hiring session, we compare the top elements of both heaps, select the smallest, and then replace it with the next candidate from that side if there are remaining unprocessed workers. This ensures each hiring session takes O(log candidates) time and overall complexity is O(k log candidates), which is acceptable given the constraints.

Algorithm Walkthrough

1. Initialize two min-heaps, left_heap and right_heap, to store tuples of (cost, index) for the first candidates and last candidates workers respectively. If the total number of workers is less than 2 * candidates, make sure not to overlap workers in both heaps.

2. Keep track of the next available index for the left and right sides, l and r, starting just beyond the initial heap windows.

3. Initialize a variable total_cost to 0.

4. Repeat k times:

5. Compare the smallest elements in left_heap and right_heap.

6. Select the one with the smaller cost. In case of a tie, select from left_heap (ensures the smallest index is chosen).

7. Add the selected cost to total_cost.

8. If the selected heap has remaining workers outside the current heap window, push the next worker into the heap and increment/decrement l or r accordingly.

9. Return total_cost.

Why it works: The algorithm maintains the invariant that both heaps always contain the current first and last available candidates. By always comparing the smallest elements from each heap, we ensure that we are selecting the globally smallest cost among allowed candidates in each session. This guarantees correctness while maintaining efficiency.

Python Solution

from typing import List
import heapq

class Solution:
    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:
        n = len(costs)
        total_cost = 0
        
        left_heap, right_heap = [], []
        l, r = candidates, n - candidates - 1
        
        for i in range(candidates):
            heapq.heappush(left_heap, (costs[i], i))
        
        for i in range(max(candidates, n - candidates), n):
            heapq.heappush(right_heap, (costs[i], i))
        
        for _ in range(k):
            if left_heap and right_heap:
                if left_heap[0] <= right_heap[0]:
                    cost, idx = heapq.heappop(left_heap)
                    total_cost += cost
                    if l <= r:
                        heapq.heappush(left_heap, (costs[l], l))
                        l += 1
                else:
                    cost, idx = heapq.heappop(right_heap)
                    total_cost += cost
                    if l <= r:
                        heapq.heappush(right_heap, (costs[r], r))
                        r -= 1
            elif left_heap:
                cost, idx = heapq.heappop(left_heap)
                total_cost += cost
            else:
                cost, idx = heapq.heappop(right_heap)
                total_cost += cost
        
        return total_cost

This Python solution creates two min-heaps for the first and last candidates and uses pointers to maintain the current candidate windows. Each hiring session pops the smallest cost worker and replenishes the heap if unprocessed workers remain. The process repeats k times to compute the total hiring cost.

Go Solution

package main

import (
	"container/heap"
)

type Worker struct {
	cost int
	index int
}

type MinHeap []Worker

func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool {
	if h[i].cost == h[j].cost {
		return h[i].index < h[j].index
	}
	return h[i].cost < h[j].cost
}
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(Worker)) }
func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	item := old[n-1]
	*h = old[:n-1]
	return item
}

func totalCost(costs []int, k int, candidates int) int64 {
	n := len(costs)
	var total int64
	leftHeap := &MinHeap{}
	rightHeap := &MinHeap{}
	heap.Init(leftHeap)
	heap.Init(rightHeap)
	l, r := candidates, n - candidates - 1

	for i := 0; i < candidates && i < n; i++ {
		heap.Push(leftHeap, Worker{costs[i], i})
	}
	for i := max(candidates, n - candidates); i < n; i++ {
		heap.Push(rightHeap, Worker{costs[i], i})
	}

	for i := 0; i < k; i++ {
		if leftHeap.Len() > 0 && rightHeap.Len() > 0 {
			if (*leftHeap)[0].cost < (*rightHeap)[0].cost || ((*leftHeap)[0].cost == (*rightHeap)[0].cost && (*leftHeap)[0].index < (*rightHeap)[0].index) {
				w := heap.Pop(leftHeap).(Worker)
				total += int64(w.cost)
				if l <= r {
					heap.Push(leftHeap, Worker{costs[l], l})
					l++
				}
			} else {
				w := heap.Pop(rightHeap).(Worker)
				total += int64(w.cost)
				if l <= r {
					heap.Push(rightHeap, Worker{costs[r], r})
					r--
				}
			}
		} else if leftHeap.Len() > 0 {
			w := heap.Pop(leftHeap).(Worker)
			total += int64(w.cost)
		} else {
			w := heap.Pop(rightHeap).(Worker)
			total += int64(w.cost)
		}
	}
	return total
}

func max(a, b int) int {
	if a > b { return a }
	return b
}

The Go solution mirrors the Python logic but uses a custom MinHeap type to handle heap operations with tie-breaking on index. Go-specific details include using int64 for total to avoid overflow and careful handling of slice indices.

Worked Examples

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

Example 2: `costs = [