Total Cost to Hire K Workers

Updated on 15 July, 2025
Total Cost to Hire K Workers header image

Problem Statement

In this problem, you are given an array costs, where each element costs[i] represents the cost of hiring the i-th worker. The workers are indexed starting from 0. Additionally, two integers k and candidates are provided, where k is the number of workers you need to hire and candidates indicates the number of workers considered for hiring in each session.

The hiring process consists of k sessions, with the stipulation that in each session, you select the worker with the minimum cost from either the first candidates workers or the last candidates workers of the unselected worker pool. If there is a tie in cost, then the worker with the smaller index is selected.

The challenge involves ensuring that the total hiring cost after k sessions is minimized, given the constraints and flavor of the selection process which dynamically changes after each hiring.

Examples

Example 1

Input:

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

Output:

11

Explanation:

We hire 3 workers in total. The total cost is initially 0.
- In the first hiring round we choose the worker from [17,12,10,2,7,2,11,20,8]. The lowest cost is 2, and we break the tie by the smallest index, which is 3. The total cost = 0 + 2 = 2.
- In the second hiring round we choose the worker from [17,12,10,7,2,11,20,8]. The lowest cost is 2 (index 4). The total cost = 2 + 2 = 4.
- In the third hiring round we choose the worker from [17,12,10,7,11,20,8]. The lowest cost is 7 (index 3). The total cost = 4 + 7 = 11. Notice that the worker with index 3 was common in the first and last four workers.
The total hiring cost is 11.

Example 2

Input:

costs = [1,2,4,1], k = 3, candidates = 3

Output:

4

Explanation:

We hire 3 workers in total. The total cost is initially 0.
- In the first hiring round we choose the worker from [1,2,4,1]. The lowest cost is 1, and we break the tie by the smallest index, which is 0. The total cost = 0 + 1 = 1. Notice that workers with index 1 and 2 are common in the first and last 3 workers.
- In the second hiring round we choose the worker from [2,4,1]. The lowest cost is 1 (index 2). The total cost = 1 + 1 = 2.
- In the third hiring round there are less than three candidates. We choose the worker from the remaining workers [2,4]. The lowest cost is 2 (index 0). The total cost = 2 + 2 = 4.
The total hiring cost is 4.

Constraints

  • 1 <= costs.length <= 105
  • 1 <= costs[i] <= 105
  • 1 <= k, candidates <= costs.length

Approach and Intuition

To solve the problem of hiring k workers with minimal cost under the constraints given, a strategic approach that iterates through each session and selects the optimal worker per session can be employed. Here's the elucidated plan:

  1. Initialize the total hiring cost to zero.
  2. For each of the k sessions:
    • Examine both the beginning and ending segments of the costs list (restricted by candidates).
    • Identify and select the minimum cost worker from these segments. If multiple workers have the same cost, select the one with the smallest index.
    • Update the total hiring cost and repeat the process for the next session, ensuring that the already selected workers are not considered.
    • Adjust the range of selectable workers for every session as the costs list diminishes after each hiring.
  3. The goal is to preserve the minimal hiring path through strategic selections, primarily influenced by the available candidates and their positions.

With this approach, the total cost accrued by the end of k sessions is hoped to be minimized effectively given the dynamic and strategically constrained selection of workers. By always choosing the lowest costs from constrained subsets, and considering fewer candidates when candidates exceed remaining workers, the solution respects the problem's detailed requirements and real-world scenario of constrained resource selection for optimal results.

Solutions

  • Java
java
class Solution {
    public long calculateMinimumCost(int[] pricing, int numWorkers, int numCandidates) {
        // Priority queue based on cost and index for tie-breaking
        PriorityQueue<int[]> queue = new PriorityQueue<>((worker1, worker2) -> {
            if (worker1[0] == worker2[0]) {
                return worker1[1] - worker2[1];
            }
            return worker1[0] - worker2[0];
        });
    
        // Initialize priority queue with first `numCandidates` from start and end
        for (int i = 0; i < numCandidates; i++) {
            queue.offer(new int[] {pricing[i], 0});
        }
        for (int i = Math.max(numCandidates, pricing.length - numCandidates); i < pricing.length; i++) {
            queue.offer(new int[] {pricing[i], 1});
        }
    
        long sum = 0;
        int forwardIndex = numCandidates;
        int backwardIndex = pricing.length - 1 - numCandidates;
    
        for (int i = 0; i < numWorkers; i++) {
            int[] currentWorker = queue.poll();
            int price = currentWorker[0], sectionId = currentWorker[1];
            sum += price;
    
            // Add next available workers based on the section
            if (forwardIndex <= backwardIndex) {
                if (sectionId == 0) {
                    queue.offer(new int[]{pricing[forwardIndex], 0});
                    forwardIndex++;
                } else {
                    queue.offer(new int[]{pricing[backwardIndex], 1});
                    backwardIndex--;
                }
            }
        }
    
        return sum;
    }
}

The code in question uses a Java class method calculateMinimumCost to calculate the minimum total cost of hiring a specific number of workers (numWorkers) from a given pool of candidates defined in the pricing array. The candidates are chosen from both the start and the end of the given array, taking into consideration numCandidates.

This method involves:

  • Utilizing a priority queue (min-heap) to efficiently select candidates based on their pricing while maintaining a balance between those considered from the beginning versus the end of the list. Workers are compared first by price, and ties are resolved using their index.

  • Initializing this queue by adding the first numCandidates from both the beginning and the end of the array.

  • Iterating through the workers needed (numWorkers), dequeueing the lowest-priced candidate, adding his price to a running total sum, and then if more candidates are needed, pulling the next candidate from the relevant section of the array based on the location of the last dequeued candidate.

The process ensures that selection is cost-effective yet balanced from different sections of the candidate pool for a diverse selection. You successfully manage costs and achieve the target hiring numbers using efficient data structures like a priority queue, which streamlines the selection process significantly.

  • Python
python
class Calculator:
    def computeTotalExpense(self, expenseList: List[int], count: int, numCandidates: int) -> int:
        priority_queue = []
        for index in range(numCandidates):
            priority_queue.append((expenseList[index], 0))
        for index in range(max(numCandidates, len(expenseList) - numCandidates), len(expenseList)):
            priority_queue.append((expenseList[index], 1))
    
        heapify(priority_queue)
            
        total_expense = 0
        next_front, next_end = numCandidates, len(expenseList) - 1 - numCandidates 
    
        for _ in range(count): 
            current_cost, section_id = heappop(priority_queue)
            total_expense += current_cost
            if next_front <= next_end: 
                if section_id == 0:
                    heappush(priority_queue, (expenseList[next_front], 0))
                    next_front += 1
                else:
                    heappush(priority_queue, (expenseList[next_end], 1))
                    next_end -= 1
                        
        return total_expense

The code provided in Python determines the total expense of hiring a specified number of workers (count) from a list of potential hire expenses (expenseList). The Calculator class contains the method computeTotalExpense, which implements a priority queue to efficiently manage and compute the hiring cost.

The algorithm operates as follows:

  1. Initialize an empty list priority_queue to store each candidate's expense and a section identifier indicating their position in the original list.
  2. The first numCandidates elements from expenseList have their costs added to the priority_queue with a section identifier of 0.
  3. Additional elements from expenseList, beyond the first numCandidates up to the remaining list size minus numCandidates, are then added with a section identifier of 1.
  4. The list is transformed into a heap structure to ensure that the smallest elements can be accessed quickly.
  5. Intialize total_expense to 0, and calculate two indices, next_front and next_end, which help track the next candidates from the initial and latter sections of the list respectively.
  6. Iterate over the number of hires (count), remove the lowest expense from the heap using heappop and add this to total_expense.
  7. Depending on which section the removed element belongs to, push the next appropriate candidate into the heap from either the beginning or end of the list while adjusting the tracking indices (next_front or next_end).

This method efficiently minimizes the total hiring cost by always selecting the next lowest available expense from the list. The use of a priority queue (heap) allows the algorithm to efficiently manage and retrieve minimum values, which is vital to achieving a cost-effective solution for hiring multiple workers.

Comments

No comments yet.