Sponsored
Sponsored
In this approach, we use a min-heap to keep track of the candidate workers with the lowest costs. By maintaining a collection of candidate workers from both ends of the list, the algorithm efficiently selects and removes the minimum worker for each session. This helps follow the hierarchical hiring order by prioritizing the smallest cost and index.
Time Complexity: O(k * log(candidates)), where k is the number of workers to hire and candidates the number from both ends considered.
Space Complexity: O(candidates) for maintaining the two heaps.
1function totalCost(costs, k, candidates) {
2 let minHeap = new MinHeap();
3 let left = [...costs.slice(0, candidates)].map((cost, i) => [cost, i]);
4 let right = [...costs.slice(-candidates)].map((cost, i) => [cost, costs.length - candidates + i]);
5
6 left.forEach(worker => minHeap.insert(worker));
7 right.forEach(worker => minHeap.insert(worker));
8
9 let totalCost = 0;
10 let hired = new Set();
11
12 while (k > 0 && !minHeap.isEmpty()) {
13 let [cost, index] = minHeap.extractMin();
14 if (hired.has(index)) continue;
15 totalCost += cost;
16 hired.add(index);
17 k--;
18 }
19
20 return totalCost;
21}
22
23class MinHeap {
24 constructor() {
25 this.heap = [];
26 }
27
28 insert(value) {
29 this.heap.push(value);
30 this.bubbleUp();
31 }
32
33 bubbleUp() {
34 let index = this.heap.length - 1;
35 const last = this.heap[index];
36 while (index > 0) {
37 let parentIndex = Math.floor((index - 1) / 2);
38 if (this.heap[parentIndex][0] <= last[0]) break;
39 this.heap[index] = this.heap[parentIndex];
40 index = parentIndex;
41 }
42 this.heap[index] = last;
43 }
44
45 extractMin() {
46 const min = this.heap[0];
47 const end = this.heap.pop();
48 if (this.heap.length) {
49 this.heap[0] = end;
50 this.sinkDown();
51 }
52 return min;
53 }
54
55 sinkDown() {
56 let index = 0;
57 const length = this.heap.length;
58 const element = this.heap[index];
59
60 while (true) {
61 let leftChildIndex = 2 * index + 1;
62 let rightChildIndex = 2 * index + 2;
63 let leftChild, rightChild;
64 let swap = null;
65
66 if (leftChildIndex < length) {
67 leftChild = this.heap[leftChildIndex];
68 if (leftChild[0] < element[0]) swap = leftChildIndex;
69 }
70
71 if (rightChildIndex < length) {
72 rightChild = this.heap[rightChildIndex];
73 if (
74 (swap === null && rightChild[0] < element[0]) ||
75 (swap !== null && rightChild[0] < leftChild[0])
76 ) swap = rightChildIndex;
77 }
78
79 if (swap === null) break;
80
81 this.heap[index] = this.heap[swap];
82 index = swap;
83 }
84 this.heap[index] = element;
85 }
86
87 isEmpty() {
88 return this.heap.length === 0;
89 }
90}
91
92// Example usage:
93console.log(totalCost([17,12,10,2,7,2,11,20,8], 3, 4));
94console.log(totalCost([1,2,4,1], 3, 3));This JavaScript implementation uses a custom MinHeap class to efficiently manage the candidate workers. The heap is manipulated to always provide the worker with the lowest cost, considering ties by index, similar to a priority queue.
This approach involves sorting segments of the array and using two pointers to dynamically track the smallest available candidate from the start and end. By maintaining sorted sections, it allows for efficient extraction by moving pointers closer as sessions proceed.
Time Complexity: O(n log candidates) to sort.
Space Complexity: O(candidates) for storing and sorting the two halves.
1import java.util.Arrays;
2
3
Java's implementation sorts both sides of potential workers and uses a pointer comparison method to decide the sequence of hiring decisions. As it hires, it adds the selected worker to the total cost after each session.