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));

1#include <vector>
2#include <algorithm>
3using namespace std;
4
5int totalCost(vector<int>& costs, int k, int candidates) {
    vector<pair<int, int>> left(costs.begin(), costs.begin() + candidates);
    vector<pair<int, int>> right(costs.end() - candidates, costs.end());

    sort(left.begin(), left.end());
    sort(right.begin(), right.end());

    int totalCost = 0;
    int l_ptr = 0, r_ptr = 0;

    for (int i = 0; i < k; ++i) {
        if (l_ptr < candidates && (r_ptr >= candidates || left[l_ptr].first <= right[r_ptr].first)) {
            totalCost += left[l_ptr].first;
            l_ptr++;
        } else {
            totalCost += right[r_ptr].first;
            r_ptr++;
        }
    }
    return totalCost;
}

// Example usage:
// vector<int> costs = {17,12,10,2,7,2,11,20,8};
// cout << totalCost(costs, 3, 4);