Total Cost to Hire K Workers Problem Solution In C++/Java/Python/Javascript
Problem Description
You are given a 0-indexed integer array costs where costs[i] is the cost of hiring the ith worker.
You are also given two integers k and candidates. We want to hire exactly k workers according to the following rules:
You will run k sessions and hire exactly one worker in each session.
In each hiring session, choose the worker with the lowest cost from either the first candidates workers or the last candidates workers. Break the tie by the smallest index.
For example, if costs = [3,2,7,7,1,2] and candidates = 2, then in the first hiring session, we will choose the 4th worker because they have the lowest cost [3,2,7,7,1,2].
In the second hiring session, we will choose 1st worker because they have the same lowest cost as 4th worker but they have the smallest index [3,2,7,7,1,2].. Please note that the indexing may be changed in the process.
If there are fewer than candidates workers remaining, choose the worker with the lowest cost among them. Break the tie by the smallest index.
A worker can only be chosen once.
Return the total cost to hire exactly k workers.
Example
Total Cost to Hire K Workers examples are as follows
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.
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 <= 10^5
- 1 <= costs[i] <= 10^5
- 1 <= k, candidates <= costs.length
The problem provides an array of hiring costs and requires you to hire exactly k workers. Now is there any way so that in each operation we could choose the best worker from either side optimally without much computations.
Sub-Optimal Approach
Real World Example
Intuition
Total Cost to Hire K Workers example in real world would follow as :Imagine you're a talent scout organizing auditions for a major show, and the hopefuls are lined up in two distinct groups—those entering from the front and those arriving from the back. You have limited time, so you only consider a select few from each end at any moment. Now you have quickly determine who is the best i.e with loer hiring cost. So,what would you do? Will you always traverse upon all the candidates and always check which is best candidate.This might be well till there are less candidates but when the count of candidates rise heavily this might be computationally expensive. So,we would need a way so that if we feed the data of workers to it,we would get the best worker instantly.
This is exactly what a heap does: it always presents you with the top candidate immediately, without having to re-examine every individual.To quickly determine who has the best performance (or in our case, the lowest hiring cost), you use a heap that automatically ranks the candidates by their skill level.
What is Heap?
A heap is a specialized tree-based data structure often used to implement priority queues. In a min-heap, the smallest element is always at the root, meaning each parent node is less than or equal to its children; in a max-heap, the largest element is at the root. Heaps are usually implemented as complete binary trees (every level is fully filled except possibly the last, and all nodes are as far left as possible), which allows them to be efficiently stored in an array. With a heap, you can quickly access the minimum or maximum element in constant time, and insertion or deletion operations take logarithmic time. This makes heaps extremely useful in algorithms that require repeated retrieval of the "best" element, like scheduling tasks or sorting data with heapsort.
What is min-heap?
A min-heap is a specialized binary tree-based data structure where the smallest element is always at the root. This means that for any given node in the tree, its value is less than or equal to the values of its children. Because of this property, you can quickly access the minimum element at any time. Additionally, a min-heap is usually implemented as a complete binary tree, which means all levels of the tree are fully filled except possibly the last level, and all nodes in the last level are as far left as possible.
What is max-heap?
A max-heap is a complete binary tree data structure where every parent node has a value greater than or equal to its children, ensuring that the largest element is always at the root. This property makes it easy to quickly access the maximum element. Like a min-heap, a max-heap is typically implemented using an array, which efficiently represents the complete binary tree.
General Operations on Heap:
- Insertion:
Inserting an element takes O(log n) time because after placing the new element at the end of the array, you "bubble up" (or "sift up") to restore the heap property. - Removal (Extract-Min/Extract-Max):
Removing the root element (the minimum in a min-heap or maximum in a max-heap) also takes O(log n) time since after removal, you "bubble down" (or "sift down") the last element placed at the root to reestablish the heap property. - Peek (Find-Min/Find-Max):
Retrieving the root element is an O(1) operation because it is always at the front of the array. - Building a Heap:
Building a heap from an unsorted array can be done in O(n) time using a bottom-up heapify process. - Space Complexity:
The heap uses O(n) space to store n elements.
Now, because you have two groups, you maintain two separate heap—one for the front group and one for the back group. Think of it like having two dedicated panels, each keeping an updated list of the best performers from their respective groups. Every time you pick a top performer from one panel, you refresh that panel by adding the next hopeful in line, ensuring that both panels always reflect the most current talent available.
This dual-queue system is not just efficient—it’s essential for handling the dynamic nature of the auditions. By having two heap, you can quickly compare the best of the front group with the best of the back group at every decision point. This ensures that you're always selecting the overall best candidate from both ends, streamlining the process while adhering to the fairness of the original lineup. In essence, the use of two heap allows you to manage and update your candidate pools effectively, just as a seasoned talent scout would in a fast-paced audition scenario.
How does the tie-breaking work when both queues have the same minimum cost?
If the minimum costs from both heaps are identical, the candidate from the head (front) heap is chosen because they naturally have the smaller index in the original list. This rule aligns with the problem's requirement of choosing the worker with the smallest index in case of a tie.
Approach
Step 1: Initialize Two heaps
Create two min-heaps : one for the front candidates (head_workers) and one for the rear candidates (tail_workers).
Step 2: Populate the Initial Candidates
Add the first candidates workers from the costs array to the head_workers heap.
Add the last candidates workers from the costs array to the tail_workers heap.
Note: If the two ranges overlap (i.e., if the total number of workers is less than or equal to 2 * candidates), ensure that each worker is added only once.
Step 3: Set Up Pointers for New Candidates
Define a pointer next_head starting at index candidates (the next worker after the initial head candidates).
Define a pointer next_tail starting at index n - candidates - 1 (the worker immediately before the initial tail candidates).
Step 4: Initialize the Total Cost
Set a variable total_cost to 0. This will accumulate the cost of the hired workers.
Step 5: Process Hiring Rounds (Repeat for k Rounds)
Compare and Select:
Look at the minimum element at the top of both head_workers and tail_workers.
If both heaps have candidates, compare their costs. Hire the worker with the lower cost.
If the costs are equal, hire the worker from the head_workers (because it corresponds to the lower index).
If one heap is empty, select the candidate from the non-empty heap.
Update Total Cost:
Add the cost of the selected worker to total_cost.
Refill the heap:
If the worker was chosen from head_workers and next_head is within bounds (i.e., next_head ≤ next_tail), add costs[next_head] to head_workers and increment next_head.
If the worker was chosen from tail_workers and there are more candidates available (i.e., next_head ≤ next_tail), add costs[next_tail] to tail_workers and decrement next_tail.
Step 6: Termination
Once you have completed k hiring rounds, return the total_cost as the final answer.
Dry Run
Total Cost to Hire K Workers Algorithm includes following steps
Step 1: Initialization
- Head Candidates: Select the first 4 workers from costs: [17, 12, 10, 2] (indices 0–3).
- Tail Candidates: Select the last 4 workers from costs: [2, 11, 20, 8] (indices 5–8).
- Pointers:
Set next_head to index 4 (next available worker after the head candidates).
Set next_tail to index 4 (calculated as n - candidates - 1, where n = 9).
Step 2: Hiring Round 1
- Compare:
Head minimum is 2 (from index 3).
Tail minimum is 2 (from index 5). - Decision: Since both costs are equal, choose the head candidate (index 3).
- Action:
Hire worker at index 3 with cost 2.
Update total_cost: 0 + 2 = 2.
Remove the worker from the head heap. - Refill:
Add the worker at next_head (index 4, cost 7) to the head heap.
Increment next_head to 5.
Step 3: Hiring Round 2
- Heaps Now:
Head heap: [17, 12, 10, 7] (minimum is 7 from index 4).
Tail heap: [2, 11, 20, 8] (minimum is still 2 from index 5). - Compare:
Head minimum is 7.
Tail minimum is 2. - Decision: Choose the tail candidate (index 5) because 2 < 7.
- Action:
Hire worker at index 5 with cost 2.
Update total_cost: 2 + 2 = 4.
Remove the worker from the tail heap. - Refill:
Check if refill is possible: next_tail is 4, but now next_head is 5, so no candidate is available to add.
Step 4: Hiring Round 3
- Heaps Now:
Head heap: [17, 12, 10, 7] (minimum is 7 from index 4).
Tail heap: [11, 20, 8] (minimum is 8). - Compare:
Head minimum is 7.
Tail minimum is 8. - Decision: Choose the head candidate (index 4) because 7 < 8.
- Action:
Hire worker at index 4 with cost 7.
Update total_cost: 4 + 7 = 11.
Remove the worker from the head heap. - Refill:
No refill available since next_head (5) > next_tail (4).
Step 5: Termination
- After 3 hiring rounds, the total cost is 11.
- Return 11 as the final answer.
Code for All Languages
Total Cost to Hire K Workers solution in C++ :Sub-Optimal
class Solution {
public:
long long totalCost(vector<int>& costs, int k, int candidates) {
int n = costs.size();
// Min-heaps for the head and tail candidate pools.
priority_queue<long long, vector<long long>, greater<long long>> head;
priority_queue<long long, vector<long long>, greater<long long>> tail;
// Determine the initial ranges to add.
// Add first 'candidates' from the front.
int left_end = min(candidates, n);
// Add last 'candidates' from the end, avoiding duplicates.
int right_start = max(candidates, n - candidates);
// Populate the head min-heap.
for (int i = 0; i < left_end; i++) {
head.push(costs[i]);
}
// Populate the tail min-heap.
for (int i = right_start; i < n; i++) {
tail.push(costs[i]);
}
// Pointers to the next available candidate in the middle.
int next_head = left_end; // Next candidate index for head.
int next_tail = right_start - 1; // Next candidate index for tail.
long long total_cost = 0;
// Process k hiring rounds.
for (int hired = 0; hired < k; hired++) {
// Decide from which heap to pick.
if (head.empty()) {
// Only tail candidates are available.
total_cost += tail.top();
tail.pop();
if (next_tail >= next_head) {
tail.push(costs[next_tail]);
next_tail--;
}
} else if (tail.empty()) {
// Only head candidates are available.
total_cost += head.top();
head.pop();
if (next_head <= next_tail) {
head.push(costs[next_head]);
next_head++;
}
} else {
// Both heaps have candidates.
// If costs are equal, head is preferred (tie-breaker).
if (head.top() <= tail.top()) {
total_cost += head.top();
head.pop();
if (next_head <= next_tail) {
head.push(costs[next_head]);
next_head++;
}
} else {
total_cost += tail.top();
tail.pop();
if (next_tail >= next_head) {
tail.push(costs[next_tail]);
next_tail--;
}
}
}
}
return total_cost;
}
};Total Cost to Hire K Workers solution in Java:Sub-Optimal
import java.util.PriorityQueue;
public class Solution {
public long totalCost(int[] costs, int k, int candidates) {
int n = costs.length;
// Create two min-heaps for head and tail candidates.
PriorityQueue<Integer> head = new PriorityQueue<>();
PriorityQueue<Integer> tail = new PriorityQueue<>();
// Populate the initial head candidates.
int leftEnd = Math.min(candidates, n);
for (int i = 0; i < leftEnd; i++) {
head.offer(costs[i]);
}
// Populate the initial tail candidates.
int rightStart = Math.max(candidates, n - candidates);
for (int i = rightStart; i < n; i++) {
tail.offer(costs[i]);
}
// Set up pointers for the next candidates from the middle.
int nextHead = leftEnd;
int nextTail = rightStart - 1;
long totalCost = 0;
// Process k hiring rounds.
for (int hired = 0; hired < k; hired++) {
if (head.isEmpty()) {
// If head is empty, choose from tail.
totalCost += tail.poll();
if (nextTail >= nextHead) {
tail.offer(costs[nextTail]);
nextTail--;
}
} else if (tail.isEmpty()) {
// If tail is empty, choose from head.
totalCost += head.poll();
if (nextHead <= nextTail) {
head.offer(costs[nextHead]);
nextHead++;
}
} else {
// Both heaps have candidates. Compare and choose.
if (head.peek() <= tail.peek()) {
totalCost += head.poll();
if (nextHead <= nextTail) {
head.offer(costs[nextHead]);
nextHead++;
}
} else {
totalCost += tail.poll();
if (nextTail >= nextHead) {
tail.offer(costs[nextTail]);
nextTail--;
}
}
}
}
return totalCost;
}
}
Total Cost to Hire K Workers solution in Python :Sub-Optimal
from typing import List
import heapq
class Solution:
def totalCost(self, costs: List[int], k: int, candidates: int) -> int:
n = len(costs)
head, tail = [], []
# Determine the initial ranges:
leftEnd = min(candidates, n)
rightStart = max(candidates, n - candidates)
# Populate the head heap with the first 'candidates' workers.
for i in range(leftEnd):
heapq.heappush(head, (costs[i], i))
# Populate the tail heap with the last 'candidates' workers,
# ensuring we don't add duplicates if the ranges overlap.
for i in range(rightStart, n):
heapq.heappush(tail, (costs[i], i))
total_cost = 0
next_head = leftEnd # Pointer for the next worker for the head heap.
next_tail = rightStart - 1 # Pointer for the next worker for the tail heap.
# Process k hiring rounds.
for _ in range(k):
# If one heap is empty, choose from the other.
if not head:
cost, idx = heapq.heappop(tail)
total_cost += cost
if next_tail >= next_head:
heapq.heappush(tail, (costs[next_tail], next_tail))
next_tail -= 1
elif not tail:
cost, idx = heapq.heappop(head)
total_cost += cost
if next_head <= next_tail:
heapq.heappush(head, (costs[next_head], next_head))
next_head += 1
else:
# Both heaps have candidates; pick the worker with the lower cost.
# If costs are equal, the head candidate is preferred (as it has a lower index).
if head[0][0] <= tail[0][0]:
cost, idx = heapq.heappop(head)
total_cost += cost
if next_head <= next_tail:
heapq.heappush(head, (costs[next_head], next_head))
next_head += 1
else:
cost, idx = heapq.heappop(tail)
total_cost += cost
if next_tail >= next_head:
heapq.heappush(tail, (costs[next_tail], next_tail))
next_tail -= 1
return total_cost
Total Cost to Hire K Workers solution in Javascript :Sub-Optimal
/**
* @param {number[]} costs
* @param {number} k
* @param {number} candidates
* @return {number}
*/
var totalCost = function(costs, k, candidates) {
// Custom MinHeap class to manage [cost, index] pairs.
class MinHeap {
constructor() {
this.heap = [];
}
parent(i) {
return Math.floor((i - 1) / 2);
}
left(i) {
return 2 * i + 1;
}
right(i) {
return 2 * i + 2;
}
swap(i, j) {
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
}
push(val) {
this.heap.push(val);
this.heapifyUp();
}
heapifyUp() {
let index = this.heap.length - 1;
while (index > 0) {
let parentIndex = this.parent(index);
// Compare based on cost; if equal, compare index.
if (
this.heap[parentIndex][0] > this.heap[index][0] ||
(this.heap[parentIndex][0] === this.heap[index][0] &&
this.heap[parentIndex][1] > this.heap[index][1])
) {
this.swap(parentIndex, index);
index = parentIndex;
} else {
break;
}
}
}
pop() {
if (this.heap.length === 0) return null;
this.swap(0, this.heap.length - 1);
const min = this.heap.pop();
this.heapifyDown(0);
return min;
}
heapifyDown(index) {
let smallest = index;
const leftIndex = this.left(index);
const rightIndex = this.right(index);
if (leftIndex < this.heap.length) {
if (
this.heap[leftIndex][0] < this.heap[smallest][0] ||
(this.heap[leftIndex][0] === this.heap[smallest][0] &&
this.heap[leftIndex][1] < this.heap[smallest][1])
) {
smallest = leftIndex;
}
}
if (rightIndex < this.heap.length) {
if (
this.heap[rightIndex][0] < this.heap[smallest][0] ||
(this.heap[rightIndex][0] === this.heap[smallest][0] &&
this.heap[rightIndex][1] < this.heap[smallest][1])
) {
smallest = rightIndex;
}
}
if (smallest !== index) {
this.swap(index, smallest);
this.heapifyDown(smallest);
}
}
peek() {
return this.heap[0];
}
size() {
return this.heap.length;
}
}
const n = costs.length;
const head = new MinHeap();
const tail = new MinHeap();
// Determine initial ranges and populate the heaps.
const leftEnd = Math.min(candidates, n);
const rightStart = Math.max(candidates, n - candidates);
for (let i = 0; i < leftEnd; i++) {
head.push([costs[i], i]);
}
for (let i = rightStart; i < n; i++) {
tail.push([costs[i], i]);
}
let nextHead = leftEnd; // Next candidate index for head.
let nextTail = rightStart - 1; // Next candidate index for tail.
let total = 0;
// Process k hiring rounds.
for (let i = 0; i < k; i++) {
if (head.size() === 0) {
const [cost, idx] = tail.pop();
total += cost;
if (nextTail >= nextHead) {
tail.push([costs[nextTail], nextTail]);
nextTail--;
}
} else if (tail.size() === 0) {
const [cost, idx] = head.pop();
total += cost;
if (nextHead <= nextTail) {
head.push([costs[nextHead], nextHead]);
nextHead++;
}
} else {
if (head.peek()[0] <= tail.peek()[0]) {
const [cost, idx] = head.pop();
total += cost;
if (nextHead <= nextTail) {
head.push([costs[nextHead], nextHead]);
nextHead++;
}
} else {
const [cost, idx] = tail.pop();
total += cost;
if (nextTail >= nextHead) {
tail.push([costs[nextTail], nextTail]);
nextTail--;
}
}
}
}
return total;
};Total cost to hire K workers complexity analysis:Time Complexity: O(n + k log n).
- Heap Initialization:
Head Heap: Inserting the first candidates workers. If you use a heapify operation, this takes O(candidates) time; otherwise, inserting each element one by one takes O(candidates log candidates).
Tail Heap: Similarly, inserting the last candidates workers takes O(candidates) with heapify, or O(candidates log candidates) when inserting one by one.
Combined: With optimal heapify, the initialization cost is O(candidates). - Processing k Hiring Rounds:
In each round, you perform a removal (pop) from one of the heaps, which is O(log candidates).
Optionally, you might insert a new candidate into the same heap, which is also O(log candidates).
Thus, each round takes O(log candidates) time.
For k rounds, the total time for this phase is O(k log candidates). - Overall Time Complexity:
Combining the initialization and the rounds gives: O(candidates)+O(klogcandidates)
In worst-case scenarios where candidates might be close to the total number of workers n, the complexity can be viewed as O(n + k log n).
Total Cost to Hire K Workers complexity analysis: Space Complexity: O(n ).
Auxiliary Space Complexity:O(candidates)
- Heaps:
The two min-heaps store at most candidates elements each. In the worst case, this amounts to O(candidates) space for each heap. Combined, they use O(2 * candidates) space, which simplifies to O(candidates). - Additional Variables:
A few extra variables (pointers like next_head, next_tail, and an accumulator total_cost) are used, which require constant space, i.e., O(1).
Total Space Complexity:O(n + candidates)
- Input Array:
The costs array is provided as input and occupies O(n) space, where n is the number of workers. - Auxiliary Data Structures:
As calculated above, the extra space is O(candidates). - Overall Total Space:
Combining these, the total space complexity is O(n + candidates). Since candidates ≤ n, this is effectively O(n).
The Sub-Optimal approach with two heaps efficiently maintains separate heaps for the first m and last m candidates, ensuring the lowest-cost worker is hired each time. However, maintaining two heaps adds extra space overhead and requires additional logic to manage both. The optimal approach improves upon this by using a single heap and section IDs to differentiate front and back candidates, reducing space complexity while still ensuring correct worker selection. This transition simplifies the implementation while maintaining efficiency.
Optimal Approach
Intuition
In the optimized approach, we would think that do we really need two heaps from previous and back or can we efficiently merge them so that we would reduce our space constraints so, instead of maintaining two separate pools of candidates from the front and back, we merge them into a single heap because finally we only need best candidates though them comes up from two different heap or from a single merged heap. Merging them has advantage as this significantly reduces space complexity while ensuring that we always consider the most relevant candidates. The key idea is that a heap efficiently maintains the lowest-cost worker at the top, eliminating the need to constantly scan through all available candidates.
By leveraging a single heap, we ensure that every time a worker is hired, a new candidate from the list is added to maintain a balanced selection process. This dynamic adjustment allows us to always operate on the most cost-effective choices without redundantly storing two separate pools. Additionally, since a heap provides efficient insertion and deletion operations in O(logn)time, we can maintain an optimal hiring process that scales well even as the number of candidates grows.
Another crucial aspect of this approach is handling tie-breakers effectively. If multiple candidates have the same hiring cost, we resolve conflicts using section IDs, ensuring a deterministic and fair selection process. By always hiring the worker with the lowest cost and updating the heap dynamically, we create a streamlined and efficient hiring strategy that minimizes computational overhead while maintaining optimality.
Why do we use a (min-heap) instead of sorting the entire array
Sorting the entire array would take O(n log n) time, which is inefficient when hiring workers iteratively. Instead, a (min-heap) allows us to efficiently extract the worker with the lowest cost in O(log m) time. Since we only need to consider m candidates at a time rather than the entire array, the heap significantly reduces unnecessary operations.
Approach
Step 1: Initialize the heap
Create a min-heap to store workers. The worker with the lowest cost has the highest priority. Each worker is stored as a pair (cost, section_id), where section ID is 0 for the first m workers and 1 for the last m workers.
Step 2: Insert Initial Workers into the Heap
Add the first m workers from the beginning of the list with section ID 0. Add the last m workers from the end of the list with section ID 1. If m is large enough that the two ranges overlap, avoid duplication by adding each worker only once.
Step 3: Initialize Pointers for New Candidates
Set up two pointers to track the next workers to be added next_head = m points to the first unselected worker from the left. next_tail = n - m - 1 points to the first unselected worker from the right. These pointers ensure that as we hire workers, we keep refilling the heap with new candidates from the middle of the list.
Step 4: Initialize the Total Cost Variable
Set total_cost = 0 to accumulate the cost of the hired workers.
Step 5: Perform k Hiring Rounds
Repeat this process k times:
- Extract the top element from the heap, hiring the worker with the lowest cost.
- If multiple workers have the same cost, hire the one with the smaller section ID (head section workers are preferred).
- Add the worker’s cost to total_cost.
- If the hired worker was from the head section, add costs[next_head] to the heap and increment next_head.
- If the hired worker was from the tail section, add costs[next_tail] to the heap and decrement next_tail.
- If no more workers are left in the list, skip adding new candidates.
Step 6: Return the Final Total Cost
Once k workers have been hired, return total_cost as the final answer.
Dry Run
Total Cost to Hire K Workers Algorithm includes following steps:
Initial Setup:
- The costs array is [17, 12, 10, 2, 7, 2, 11, 20, 8].
- You are tasked to hire k = 3 workers, and there are candidates = 4 workers from both the beginning and end to choose from.
Step 1: Initialize the heap
- You initialize a heap with the first 4 workers and the last 4 workers, each marked by a section ID. Section ID 0 corresponds to the first part (head) and Section ID 1 corresponds to the last part (tail).
- The workers are added as pairs (cost, section ID).
- First 4 workers (head section): [(17, 0), (12, 0), (10, 0), (2, 0)]
- Last 4 workers (tail section): [(7, 1), (2, 1), (11, 1), (20, 1)]
- The heap is now organized with workers sorted by cost. The workers with the lowest cost will appear first in the queue, and in case of ties, the worker with the smaller section ID (head section) is preferred.
Step 2: Hiring Round 1
- Pick the worker with the lowest cost:
- The top of the heap is (2, 0) from the head section.
- This worker is hired first.
- Update the total cost:
- The total cost after this hiring is 0 + 2 = 2.
- Add the next worker from the head section:
- The next worker from the head section is at position 4 in the array (costs[4] = 7).
- This worker is added to the heap with section ID 0.
Step 3: Hiring Round 2
- Pick the worker with the lowest cost:
- The top of the heap is (2, 1) from the tail section.
- This worker is hired next.
- Update the total cost:
- The total cost after this hiring is 2 + 2 = 4.
- Add the next worker from the tail section:
- The next worker from the tail section is at position 4 from the end of the array (costs[4] = 7).
- This worker is added to the heap with section ID 1.
Step 4: Hiring Round 3
- Pick the worker with the lowest cost:
- The top of the heap is (7, 0) from the head section.
- This worker is hired next.
- Update the total cost:
- The total cost after this hiring is 4 + 7 = 11.
- Add the next worker from the head section:
- The next worker from the head section is at position 5 in the array (costs[5] = 2).
- This worker is added to the heap with section ID 0.
Final Output:
- After hiring 3 workers, the total cost is 11.
Code for All Languages
Total Cost to Hire K Workers solution in C++ :Optimal
class Solution {
public:
long totalCost(vector<int>& costs, int k, int candidates) {
// Define a priority queue to store workers with their costs and section IDs
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
// Add the first 'candidates' workers (section 0) to the priority queue
for (int i = 0; i < candidates; i++) {
pq.push({costs[i], 0});
}
// Add the last 'candidates' workers (section 1) to the priority queue
for (int i = max(candidates, (int)costs.size() - candidates); i < costs.size(); i++) {
pq.push({costs[i], 1});
}
long answer = 0;
int nextHead = candidates;
int nextTail = costs.size() - 1 - candidates;
// Hire k workers
for (int i = 0; i < k; i++) {
// Get the worker with the lowest cost (and smallest index if tie)
auto curWorker = pq.top();
pq.pop();
int curCost = curWorker.first, curSectionId = curWorker.second;
answer += curCost;
// Only refill pq if there are workers outside the current range
if (nextHead <= nextTail) {
if (curSectionId == 0) {
pq.push({costs[nextHead], 0});
nextHead++;
} else {
pq.push({costs[nextTail], 1});
nextTail--;
}
}
}
return answer;
}
};Total Cost to Hire K Workers solution in Java :Optimal
class Solution {
public long totalCost(int[] costs, int k, int candidates) {
// The worker with the lowest cost has the highest priority, if two players has the
// same cost, break the tie by their indices (0 or 1).
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
if (a[0] == b[0]) {
return a[1] - b[1];
}
return a[0] - b[0];});
// Add the first k workers with section id of 0 and
// the last k workers with section id of 1 (without duplication) to pq.
for (int i = 0; i < candidates; i++) {
pq.offer(new int[] {costs[i], 0});
}
for (int i = Math.max(candidates, costs.length - candidates); i < costs.length; i++) {
pq.offer(new int[] {costs[i], 1});
}
long answer = 0;
int nextHead = candidates;
int nextTail = costs.length - 1 - candidates;
for (int i = 0; i < k; i++) {
int[] curWorker = pq.poll();
int curCost = curWorker[0], curSectionId = curWorker[1];
answer += curCost;
// Only refill pq if there are workers outside.
if (nextHead <= nextTail) {
if (curSectionId == 0) {
pq.offer(new int[]{costs[nextHead], 0});
nextHead++;
} else {
pq.offer(new int[]{costs[nextTail], 1});
nextTail--;
}
}
}
return answer;
}
}Total Cost to Hire K Workers solution in Python :Optimal
class Solution:
def totalCost(self, costs: List[int], k: int, candidates: int) -> int:
# Add the first k workers with section id of 0 and
# the last k workers with section id of 1 (without duplication) to pq.
pq = []
for i in range(candidates):
pq.append((costs[i], 0))
for i in range(max(candidates, len(costs) - candidates), len(costs)):
pq.append((costs[i], 1))
heapify(pq)
answer = 0
next_head, next_tail = candidates, len(costs) - 1 - candidates
# Only refill pq if there are workers outside.
for _ in range(k):
cur_cost, cur_section_id = heappop(pq)
answer += cur_cost
if next_head <= next_tail:
if cur_section_id == 0:
heappush(pq, (costs[next_head], 0))
next_head += 1
else:
heappush(pq, (costs[next_tail], 1))
next_tail -= 1
return answerTotal Cost to Hire K Workers solution in Javascript :Optimal
class Solution {
totalCost(costs, k, candidates) {
// Define a priority queue to store workers with their costs and section IDs
const pq = new MinPriorityQueue({
compare: (a, b) => a[0] - b[0] || a[1] - b[1]
});
// Add the first 'candidates' workers (section 0) to the priority queue
for (let i = 0; i < candidates; i++) {
pq.push([costs[i], 0]);
}
// Add the last 'candidates' workers (section 1) to the priority queue
for (let i = Math.max(candidates, costs.length - candidates); i < costs.length; i++) {
pq.push([costs[i], 1]);
}
let answer = 0;
let nextHead = candidates;
let nextTail = costs.length - 1 - candidates;
// Hire k workers
for (let i = 0; i < k; i++) {
// Get the worker with the lowest cost (and smallest index if tie)
const curWorker = pq.pop();
const [curCost, curSectionId] = curWorker;
answer += curCost;
// Only refill pq if there are workers outside the current range
if (nextHead <= nextTail) {
if (curSectionId === 0) {
pq.push([costs[nextHead], 0]);
nextHead++;
} else {
pq.push([costs[nextTail], 1]);
nextTail--;
}
}
}
return answer;
}
}Total cost to hire K workers complexity analysis:Time Complexity O((k+m)⋅logm)
For the sake of brevity, let m be the given integer candidates.
- Time complexity: O((k+m)⋅logm)
We need to initialize one heap pq of size up to 2⋅m, which takes O(m⋅logm) time.
During k hiring rounds, we keep popping top elements from pq and pushing new elements into pq for up to k times. Operations on a heap take amortized O(logm) time. Thus this process takes O(k⋅logm) time.
Note: in Python, heapq.heapify() creates the heap in linear time. Therefore, in Python, the time complexity is O(m+k⋅logm).
Total cost to hire K workers complexity analysis: Space Complexity O(n ).
Auxiliary Space Complexity:O(candidates)
- The heap stores up to 2 * candidates workers (first m = candidates from the front and last m = candidates from the tail).
- Since the maximum size of the heap is 2 * candidates, the auxiliary space used by the heap is O(2 * candidates), which simplifies to O(candidates).
- There are no other significant data structures used that require extra space beyond the heap.
Total Space Complexity:O(candidates)
- The only data structure requiring additional space is the heap, which takes up to O(candidates) space.
- Apart from the heap, the space used by a few variables (like pointers for managing workers and the total cost) is constant.
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
Similar Problems
The problem involves managing the movement of k workers to transfer n boxes between two warehouses, with constraints on worker efficiency and bridge usage. Workers cross the bridge, pick up boxes, and deliver them, all while ensuring that no more than one worker crosses at a time and that the least efficient worker is prioritized. The challenge is to compute the total time it takes for the last box to reach the left warehouse. The process involves managing workers' crossing and delivery times while adhering to the given efficiency rules.
In the Guess Game, you need to find the number I picked between 1 and n. You make guesses, and based on the result from the guess() API, which returns -1 (too high), 1 (too low), or 0 (correct), you adjust your guesses until you identify the correct number. Your task is to return the number I picked after using the API to guide your guesses.