LeetCode Solutions Blog

Total Cost to Hire K Workers

Number: 2553

Difficulty: Medium

Paid? No

Problem Description

Given an array of worker hiring costs, you must conduct k hiring sessions. In each session you choose one worker from one of two candidate pools: the first "candidates" workers or the last "candidates" workers. The worker with the lowest cost is chosen; if costs are equal, the one with the lower index is chosen. When a worker is hired, the candidate pool from which the worker came is replenished from the remaining workers (if any). The goal is to determine the total cost to hire exactly k workers.

Key Insights

Use two candidate pools (left and right) representing the first and last portions of the array.
A min-heap (priority queue) efficiently retrieves the worker with the lowest cost; store (cost, index) to automatically break ties by index.
Maintain two pointers to track the next potential candidate in the middle after each hire.
Take care of overlapping when the candidate pools intersect.

Space and Time Complexity

Time Complexity: O(k log(candidates))
Space Complexity: O(candidates)

Solution

We use two min-heaps: one for the left candidate pool and one for the right candidate pool. Initialize the left heap with the first "candidates" workers and the right heap with the last "candidates" workers (ensuring no overlap). For each hiring session (total k sessions), compare the top elements (lowest cost and then the smallest index) from both heaps. Once a worker is hired from a heap, if there are remaining workers outside the current candidate pool, add the next available worker from that side into the heap. This simulation approach with heaps efficiently retrieves the smallest cost candidate in each session.

Code Solutions

import heapq

def totalCost(costs, k, candidates):
    n = len(costs)
    total_cost = 0
    
    # Initialize heaps for left and right candidate pools
    left_heap = []
    right_heap = []
    
    left_ptr = 0
    right_ptr = n - 1

    # Avoid overlapping candidate windows.
    for _ in range(min(candidates, n)):
        heapq.heappush(left_heap, (costs[left_ptr], left_ptr))
        left_ptr += 1
    for _ in range(min(candidates, n - left_ptr)):
        heapq.heappush(right_heap, (costs[right_ptr], right_ptr))
        right_ptr -= 1

    for _ in range(k):
        if left_heap and right_heap:
            # Compare the top elements of both heaps.
            if left_heap[0] <= right_heap[0]:
                cost, idx = heapq.heappop(left_heap)
                total_cost += cost
                if left_ptr <= right_ptr:
                    heapq.heappush(left_heap, (costs[left_ptr], left_ptr))
                    left_ptr += 1
            else:
                cost, idx = heapq.heappop(right_heap)
                total_cost += cost
                if left_ptr <= right_ptr:
                    heapq.heappush(right_heap, (costs[right_ptr], right_ptr))
                    right_ptr -= 1
        elif left_heap:
            cost, idx = heapq.heappop(left_heap)
            total_cost += cost
            if left_ptr <= right_ptr:
                heapq.heappush(left_heap, (costs[left_ptr], left_ptr))
                left_ptr += 1
        else:  # right_heap is not empty.
            cost, idx = heapq.heappop(right_heap)
            total_cost += cost
            if left_ptr <= right_ptr:
                heapq.heappush(right_heap, (costs[right_ptr], right_ptr))
                right_ptr -= 1

    return total_cost

# Example usage:
print(totalCost([17,12,10,2,7,2,11,20,8], 3, 4))  # Expected output 11