2462. Total Cost to Hire K Workers


Problem Description

You are presented with a task of hiring k workers from an array of workers where each worker has a specified hiring cost. The workers are arranged in a 0-indexed array costs, with costs[i] representing the cost of hiring the ith worker. You are to follow specific hiring rules to minimize the total hiring cost.

Here are the hiring rules:

  • You must conduct k hiring sessions, hiring one worker during each session.
  • In each session, you can only consider the first candidates or the last candidates workers for hiring.
  • You are to hire the worker with the lowest cost from these candidates. If there's a tie in the cost, you hire the worker with the smallest index.
  • If there are fewer than candidates workers left, you select from among them based on the lowest cost, again breaking ties by index.
  • Each worker can only be hired once.

After executing this hiring process exactly k times, your task is to calculate and return the total cost of hiring the k workers.

Intuition

Given the problem's constraints and the requirement to minimize the total hiring cost, it becomes evident that a greedy approach can be used to find the solution. The essence of this approach is to always pick the cheapest available worker during each hiring session.

An intuitive way to repeatedly find and hire the worker with the lowest cost is to use a min-heap, a data structure that allows us to efficiently retrieve and remove the minimum element. In each hiring session, the following operations are performed:

  1. Push the costs and indices of the first candidates workers and the last candidates workers into a min-heap after filtering out workers who were previously hired.
  2. Pop the worker with the lowest cost from the heap.
  3. Include this cost in the running total of costs.
  4. Adjust the range of workers considered for the next session to exclude the worker just hired.

To initialize this process:

  • A heap is formed with the initial candidates from both ends of the array.
  • The first hiring session is conducted by popping the cheapest worker from the heap.
  • Following each hiring session, the heap is updated by adding the next candidate from the appropriate end of the array, as long as we have not surpassed the boundaries defined by the hired workers.

This process continues until all k workers have been hired. The cumulative total at the end of the k sessions is the total cost of hiring the workers.

Solution Approach

The solution leverages a min-heap data structure to efficiently manage the workers being considered for hiring. Here is a step-by-step breakdown of the algorithm based on the solution code provided:

  1. Initialize the min-heap with candidate workers: Two pointers, i and j, are used to mark the boundary of the first and last candidates workers. The first candidates workers and the last candidates workers are pushed into the heap along with their indices. The heap is then heapified to establish the min-heap property.

    1q = []
    2n = len(costs)
    3i, j = candidates - 1, n - candidates
    4for h in range(candidates):
    5    q.append((costs[h], h))
    6for h in range(n - candidates, n):
    7    if h > i:
    8        q.append((costs[h], h))
    9heapify(q)
  2. Hire workers in k sessions: A total of k hiring sessions are to be conducted. In each session:

    • The worker with the lowest cost is popped from the heap using heappop().
    • The cost of the hired worker is added to the total cost ans.
    • Depending on the index of the worker hired, the pointers i and j are updated to ensure the correct range of candidates for the next hiring session.
    • If a worker from the first candidates (lower part of the range) is hired, the pointer i is incremented.
    • Conversely, if a worker from the last candidates (upper part of the range) is hired, the pointer j is decremented.
    • Provided there are still candidates between the updated i and j, a new worker is pushed onto the heap from the updated index position.
    1ans = 0
    2for _ in range(k):
    3    c, x = heappop(q)
    4    ans += c
    5    if x <= i:
    6        i += 1
    7        if i < j:
    8            heappush(q, (costs[i], i))
    9    if x >= j:
    10        j -= 1
    11        if i < j:
    12            heappush(q, (costs[j], j))
  3. Return the total cost: Once all k sessions are complete and k workers are hired, the accumulated total cost (ans) is returned as the answer to the problem.

    1return ans

This approach ensures that in each session, we are hiring the worker with the lowest cost from the eligible candidates by using the min-heap to efficiently find that worker. The heap is dynamically updated after each hiring to reflect the remaining candidates, and the use of pointers helps keep track of the updated range of candidates after each hiring session.

Example Walkthrough

Let's illustrate the solution approach with a small example. Assume we have an array of worker costs costs = [7, 3, 5, 1, 4, 8], we need to hire k = 3 workers, and we are allowed to consider candidates = 2 workers from each end of the array for hiring in each session.

Initial Step:

  • Initialize the min-heap with the first candidates workers ([7, 3]) and the last candidates workers ([4, 8]). The heap, after heapifying, will contain (3, 1), (7, 0), (4, 4), (8, 5) – where each tuple consists of (cost of worker, index of the worker).

Session 1:

  • Pop (3, 1), the worker with the lowest cost, from the heap. The total hiring cost ans is now 3.
  • After hiring, i becomes 2 (candidates pointer moves by one) and the min-heap is updated with the new candidate (5, 2). No need to push from the end since j has not moved. The new heap after pushing and heapifying will be (4, 4), (7, 0), (5, 2), (8, 5).

Session 2:

  • Pop (4, 4), the next worker with the lowest cost, from the heap. The total hiring cost ans is now 3 + 4 = 7.
  • After hiring, j becomes 3 (candidates pointer moves by one from the end) and the min-heap is updated with a new candidate from the end which does not exist in this case since only one candidate (5) exists between i and j. The new heap remains unchanged as (7, 0), (5, 2), (8, 5).

Session 3:

  • Pop (5, 2), the next worker with the lowest cost, from the heap. The total hiring cost ans is now 7 + 5 = 12.
  • No more workers are pushed onto the heap as the hiring sessions required (k=3) have been completed.

Final Step:

  • Return the total cost of hiring, which is 12.

This step-by-step process confirms that the presented solution approach will hire the workers with the lowest cost given the problem constraints, ensuring the total hiring cost is minimized while obeying the hiring rules.

Python Solution

1from heapq import heapify, heappop, heappush
2from typing import List
3
4class Solution:
5    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:
6        # Priority queue to store costs with their respective indices
7        priority_queue = []
8        n = len(costs)  # The total number of costs provided
9      
10        # Calculate the boundary indices for the candidates
11        left_candidate_bound = candidates - 1
12        right_candidate_bound = n - candidates
13      
14        # Populate the priority queue with the left side candidates
15        for index in range(candidates):
16            priority_queue.append((costs[index], index))
17      
18        # Populate the priority queue with the right side candidates
19        for index in range(n - candidates, n):
20            # Only add if we're past 'left_candidate_bound'
21            if index > left_candidate_bound:
22                priority_queue.append((costs[index], index))
23      
24        # Transform the priority_queue into a min-heap
25        heapify(priority_queue)
26      
27        # Variable to keep the running total cost of the selected candidates
28        total_cost = 0
29      
30        # Retrieve the smallest costs 'k' times
31        for _ in range(k):
32            # Extract the candidate with the smallest cost
33            cost, index = heappop(priority_queue)
34            total_cost += cost
35          
36            # If selected from the left side, we need to move the left boundary right
37            if index <= left_candidate_bound:
38                left_candidate_bound += 1
39                if left_candidate_bound < right_candidate_bound:
40                    heappush(priority_queue, (costs[left_candidate_bound], left_candidate_bound))
41          
42            # If selected from the right side, we need to move the right boundary left
43            if index >= right_candidate_bound:
44                right_candidate_bound -= 1
45                if left_candidate_bound < right_candidate_bound:
46                    heappush(priority_queue, (costs[right_candidate_bound], right_candidate_bound))
47      
48        return total_cost
49

Java Solution

1import java.util.PriorityQueue;
2
3class Solution {
4    public long totalCost(int[] costs, int k, int candidates) {
5        // Create a priority queue with a custom comparator
6        // The comparator orders by cost and then index
7        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> {
8            if (a[0] == b[0]) {
9                return a[1] - b[1];
10            }
11            return a[0] - b[0];
12        });
13
14        int n = costs.length;
15        int leftIndex = candidates - 1; // Left boundary of the elements added to the queue
16        int rightIndex = n - candidates; // Right boundary of the elements added to the queue
17
18        // Add initial candidates to the priority queue
19        for (int h = 0; h < candidates; ++h) {
20            queue.offer(new int[]{costs[h], h});
21        }
22
23        // Add the opposite end candidates to the priority queue
24        for (int h = n - candidates; h < n; ++h) {
25            if (h > leftIndex) {
26                queue.offer(new int[]{costs[h], h});
27            }
28        }
29
30        long totalCost = 0; // Sum of the costs
31        while (k-- > 0) {
32            int[] current = queue.poll(); // Get the least expensive element
33            int cost = current[0], index = current[1];
34            totalCost += cost; // Update the total cost
35
36            // If the element is from the left side, move right
37            if (index <= leftIndex) {
38                if (++leftIndex < rightIndex) {
39                    queue.offer(new int[]{costs[leftIndex], leftIndex});
40                }
41            }
42
43            // If the element is from the right side, move left
44            if (index >= rightIndex) {
45                if (--rightIndex > leftIndex) {
46                    queue.offer(new int[]{costs[rightIndex], rightIndex});
47                }
48            }
49        }
50
51        return totalCost; // Return the total cost after processing for k elements
52    }
53}
54

C++ Solution

1#include <vector>
2#include <queue>
3using std::vector;
4using std::priority_queue;
5using std::pair;
6
7class Solution {
8public:
9    // Calculate the total cost of selecting 'k' elements,
10    // where 'candidates' specifies how many elements at the start and end of 'costs' to consider.
11    long long totalCost(vector<int>& costs, int k, int candidates) {
12        // priority_queue that sorts based on the first element of the pair, in ascending order
13        priority_queue<pair<int, int>, vector<pair<int, int>>, std::greater<pair<int, int>>> minHeap;
14      
15        int numElements = costs.size();
16        // 'startIndex' and 'endIndex' define the bounds of the initial window of candidates
17        int startIndex = candidates - 1, endIndex = numElements - candidates;
18      
19        // Add first 'candidates' elements to the priority queue
20        for (int i = 0; i < candidates; ++i) {
21            minHeap.push({costs[i], i});
22        }
23      
24        // Add last 'candidates' elements to the priority queue, if they are not included above
25        for (int i = numElements - candidates; i < numElements; ++i) {
26            if (i > startIndex) {
27                minHeap.push({costs[i], i});
28            }
29        }
30      
31        long long totalCost = 0; // Variable to keep the total cost of 'k' elements
32        while (k--) {
33            // Extract the element with the minimum cost
34            auto [cost, index] = minHeap.top();
35            minHeap.pop();
36          
37            // Add the cost to the total
38            totalCost += cost;
39          
40            // If the element is pulled from the start window
41            if (index <= startIndex) {
42                // Move the start window to the right
43                if (++startIndex < endIndex) {
44                    minHeap.push({costs[startIndex], startIndex});
45                }
46            }
47            // If the element is pulled from the end window
48            if (index >= endIndex) {
49                // Move the end window to the left
50                if (--endIndex > startIndex) {
51                    minHeap.push({costs[endIndex], endIndex});
52                }
53            }
54        }
55      
56        return totalCost; // Return the computed total cost
57    }
58};
59

Typescript Solution

1function totalCost(costs: number[], k: number, candidates: number): number {
2    // A priority queue represented by an array that sorts elements in ascending order by cost
3    const minHeap: [number, number][] = []; // Each element is a tuple with cost and its index
4
5    // Helper function to push elements into the priority queue and then sort it
6    const pushToMinHeap = (cost: number, index: number) => {
7        minHeap.push([cost, index]);
8        minHeap.sort((a, b) => a[0] - b[0]); // sorts based on the cost which is the first element of the tuple
9    };
10
11    const numElements: number = costs.length;
12    // Starting index of the window for candidates
13    let startIndex: number = candidates - 1;
14    // Ending index of the window for candidates
15    let endIndex: number = numElements - candidates;
16
17    // Add the first 'candidates' elements to the minHeap
18    for (let i = 0; i < candidates; i++) {
19        pushToMinHeap(costs[i], i);
20    }
21
22    // Add the last 'candidates' elements to the minHeap, if they are not included above
23    for (let i = numElements - candidates; i < numElements; i++) {
24        if (i > startIndex) {
25            pushToMinHeap(costs[i], i);
26        }
27    }
28  
29    let total: number = 0; // Variable to keep track of the total cost of 'k' elements
30
31    while (k > 0) {
32        // Extract the element with the minimum cost which will be at the beginning of the sorted array
33        const [cost, index] = minHeap.shift()!; // Using '!' to reassure TypeScript that the element will always exist
34
35        // Add the cost to the total
36        total += cost;
37        k--;
38
39        // If the element is pulled from the start window
40        if (index <= startIndex) {
41            // Move the start window to the right
42            startIndex++;
43            if (startIndex < endIndex) {
44                pushToMinHeap(costs[startIndex], startIndex);
45            }
46        }
47      
48        // If the element is pulled from the end window
49        if (index >= endIndex) {
50            // Move the end window to the left
51            endIndex--;
52            if (endIndex > startIndex) {
53                pushToMinHeap(costs[endIndex], endIndex);
54            }
55        }
56    }
57
58    return total; // Return the computed total cost
59}
60
61// Usage example
62// const costs: number[] = [1, 2, 3, 4, 5];
63// const k: number = 2;
64// const candidates: number = 3;
65// console.log(totalCost(costs, k, candidates)); // This would run the function with provided arguments
66

Time and Space Complexity

Time Complexity

The main operations in the given code are:

  1. Inserting elements into the min-heap: This happens twice, once for each section of the array costs determined by the parameter candidates. It is done for the first candidates and the last candidates. This results in 2*candidates heappush operations initially and the time complexity for this operation is O(candidates * log(candidates)) for each section since each heappush operation has a time complexity of O(log(n)) where n is the number of elements in the heap at that moment.
  2. Heapifying the initial queue q with 2*candidates elements: Heapifying an array of n elements takes O(n) time, so for 2*candidates elements the complexity is O(candidates).
  3. The for loop runs k times, and in each iteration, it does a heappop operation followed by a heappush if the condition if i < j holds. The heappop is O(log(n)) for each pop, and heappush is also O(log(n)). Since at most one heappush follows each heappop in the loop and n is the size of the heap which is at most 2*candidates, the total time complexity for this loop is O(k * log(candidates)).

Adding up these costs, the overall time complexity is O(candidates * log(candidates)) + O(candidates) + O(k * log(candidates)). Since O(candidates) is subsumed by O(candidates * log(candidates)), the simplified time complexity is O(candidates * log(candidates) + k * log(candidates)).

Space Complexity

The space complexity of the algorithm is determined by:

  1. The min-heap q which has up to 2*candidates elements: So the space complexity for the heap is O(candidates).
  2. The auxiliary space for the variables i, j, ans: which is O(1).

Therefore, the overall space complexity is O(candidates) for the heap storage.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫