# Total Cost to Hire K Workers
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/total-cost-to-hire-k-workers)
Canonical: https://scaleengineer.com/dsa/problems/total-cost-to-hire-k-workers
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Array, Heap (Priority Queue)
**Companies:** [BNY Mellon](https://scaleengineer.com/companies/bny-mellon), [Zomato](https://scaleengineer.com/companies/zomato), [MathWorks](https://scaleengineer.com/companies/mathworks), [GSA Capital](https://scaleengineer.com/companies/gsa-capital)
---
## Problem
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,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 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`

# Approaches
## Brute Force Simulation
This approach directly simulates the hiring process as described in the problem statement. In each of the `k` hiring sessions, it scans the list of workers to identify the available candidates from the first and last `candidates` positions. It then finds the one with the minimum cost among this pool (breaking ties by index), adds their cost to the total, and conceptually removes them from the available pool for subsequent rounds.
**Time:** O(k * n). The outer loop runs `k` times. Inside, finding the candidates involves scanning up to `n` elements in the worst case (if using a boolean array) or `O(candidates)` if using a list but with an `O(n)` removal cost. Both variations lead to an overall complexity that is too slow. · **Space:** O(n). A boolean array or a list is used to keep track of hired/available workers, which requires space proportional to the total number of workers.
**Pros:** Simple to understand and implement as it directly models the rules given in the problem.
**Cons:** Very inefficient due to repeated full or partial scans of the `costs` array.; The time complexity of `O(k * n)` is too slow for the given constraints and will result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
To implement this simulation, we can use a boolean array, `hired`, of the same size as `costs` to keep track of which workers have already been hired. All entries are initially `false`.

We then loop `k` times. In each iteration, we need to find the best candidate for the current session. We initialize a `minCost` variable to infinity and a `minIndex` to -1. We then perform two scans:

1.  A scan from the beginning of the array to find the first `candidates` *unhired* workers. For each of these candidates, we check if they are a better choice than our current `minCost`/`minIndex` (lower cost, or same cost with a smaller index).
2.  A similar scan from the end of the array to find the last `candidates` *unhired* workers, again updating our best choice if a better candidate is found.

After these two scans, we will have identified the overall best candidate for the session. We add their cost to a running `totalCost` and mark them as hired in our `hired` array. This process repeats `k` times.

```java
class Solution {
    public long totalCost(int[] costs, int k, int candidates) {
        long totalCost = 0;
        int n = costs.length;
        // Using a list to easily remove hired workers. This is also inefficient.
        java.util.List<int[]> workerList = new java.util.ArrayList<>();
        for (int i = 0; i < n; i++) {
            workerList.add(new int[]{costs[i], i}); // {cost, original_index}
        }

        for (int i = 0; i < k; i++) {
            int minCost = Integer.MAX_VALUE;
            int minIndexInList = -1;
            int minOriginalIndex = -1;

            // Check first 'candidates' workers
            int limit = Math.min(candidates, workerList.size());
            for (int j = 0; j < limit; j++) {
                int[] worker = workerList.get(j);
                if (worker[0] < minCost || (worker[0] == minCost && worker[1] < minOriginalIndex)) {
                    minCost = worker[0];
                    minOriginalIndex = worker[1];
                    minIndexInList = j;
                }
            }

            // Check last 'candidates' workers
            int start = Math.max(0, workerList.size() - candidates);
            for (int j = start; j < workerList.size(); j++) {
                int[] worker = workerList.get(j);
                if (worker[0] < minCost || (worker[0] == minCost && worker[1] < minOriginalIndex)) {
                    minCost = worker[0];
                    minOriginalIndex = worker[1];
                    minIndexInList = j;
                }
            }

            if (minIndexInList != -1) {
                totalCost += minCost;
                workerList.remove(minIndexInList);
            }
        }
        return totalCost;
    }
}
```
### Algorithm
1. Initialize `totalCost = 0` and a boolean array `hired` of size `n` to all `false`.
2. Repeat `k` times to simulate each hiring session:
    a. Initialize `minCost` to a very large value and `minIndex` to -1.
    b. Identify the pool of candidates. This pool consists of the first `candidates` unhired workers and the last `candidates` unhired workers.
    c. To do this, first scan from the beginning of the `costs` array. For the first `candidates` workers found that are not yet hired, compare their cost with `minCost`. If a worker has a lower cost, or the same cost but a smaller index, update `minCost` and `minIndex`.
    d. Then, scan from the end of the `costs` array. For the first `candidates` workers found (from the end) that are not yet hired, perform the same comparison and update `minCost` and `minIndex` if a better candidate is found.
    e. After checking both pools, `minCost` and `minIndex` will hold the cost and index of the worker to be hired.
    f. Add `minCost` to `totalCost`.
    g. Mark the chosen worker as hired by setting `hired[minIndex] = true`.
3. After `k` sessions, return `totalCost`.

## Two Priority Queues (Heaps)
A much more efficient approach uses two min-priority queues (min-heaps) to manage the candidate pools. One priority queue, `leftPQ`, will store candidates from the beginning of the array, and another, `rightPQ`, will store candidates from the end. This structure avoids re-scanning the array in every session, as the heaps can provide the minimum-cost candidate in logarithmic time, which is a significant improvement.
**Time:** O((k + candidates) * log(candidates)). A more precise analysis shows that we perform `2*candidates` initial insertions and then `k` poll/offer operations. Each operation on a heap of size `candidates` takes `O(log(candidates))`. Thus, the total time is dominated by these heap operations. · **Space:** O(candidates). The two priority queues will hold at most `2 * candidates` elements combined, plus any workers from the middle section that are added later. The total space is bounded by the number of candidates.
**Pros:** Highly efficient for the given constraints, with a time complexity of O((k + candidates) * log(candidates)).; Effectively uses priority queues to avoid expensive re-scanning of the array.; Scales well with large inputs.
**Cons:** The implementation is more complex than a direct simulation.; Requires careful management of two data structures, pointers, and edge cases like overlapping candidate pools.
### Explanation
We maintain two pointers, `left` and `right`, to track the boundaries of the workers in the middle of the array that have not yet been considered for the candidate pools. We initialize two min-priority queues to store pairs of `[cost, index]` to handle tie-breaking correctly.

First, we populate `leftPQ` with the first `candidates` workers and `rightPQ` with the last `candidates` workers. We must handle the edge case where these two pools overlap from the start (`2 * candidates >= costs.length`) by ensuring no worker is added to both queues. The `left` and `right` pointers are then updated to point just beyond these initial pools.

We then loop `k` times for the hiring sessions. In each session:
1.  We examine the top elements of both `leftPQ` and `rightPQ`.
2.  We select the worker with the lower cost. If costs are equal, we choose the one with the smaller index (which will be the one from `leftPQ`).
3.  We add the cost of the chosen worker to `totalCost` and remove them from their priority queue.
4.  If we hired a worker, we add a new candidate to the pool if one is available. For example, if we hired from `leftPQ` and the `left` pointer is still less than or equal to the `right` pointer, we add the worker at index `left` to `leftPQ` and increment `left`. This ensures the candidate pools are always replenished from the available workers.

This process efficiently finds the cheapest worker in each round without expensive scans.

```java
import java.util.PriorityQueue;

class Solution {
    public long totalCost(int[] costs, int k, int candidates) {
        // Min-heap for the first 'candidates' workers, stores {cost, index}
        PriorityQueue<int[]> leftPQ = new PriorityQueue<>((a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0];
            }
            return a[1] - b[1];
        });

        // Min-heap for the last 'candidates' workers
        PriorityQueue<int[]> rightPQ = new PriorityQueue<>((a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0];
            }
            return a[1] - b[1];
        });

        int left = 0;
        int right = costs.length - 1;
        long totalCost = 0;

        // Loop k times to hire k workers
        for (int i = 0; i < k; i++) {
            // Fill the left PQ up to 'candidates' size, if there are workers available
            while (leftPQ.size() < candidates && left <= right) {
                leftPQ.offer(new int[]{costs[left], left});
                left++;
            }
            // Fill the right PQ up to 'candidates' size, if there are workers available
            while (rightPQ.size() < candidates && left <= right) {
                rightPQ.offer(new int[]{costs[right], right});
                right--;
            }

            int[] leftCandidate = leftPQ.peek();
            int[] rightCandidate = rightPQ.peek();

            if (leftCandidate == null && rightCandidate == null) {
                break; // No more workers to hire
            }

            // Decide which candidate to hire
            if (rightCandidate == null || (leftCandidate != null && leftCandidate[0] <= rightCandidate[0])) {
                totalCost += leftCandidate[0];
                leftPQ.poll();
            } else {
                totalCost += rightCandidate[0];
                rightPQ.poll();
            }
        }

        return totalCost;
    }
}
```
### Algorithm
1. Initialize `totalCost = 0`, and two pointers `left = 0` and `right = n - 1`.
2. Create two min-priority queues, `leftPQ` and `rightPQ`. The comparator should prioritize lower cost, then lower index.
3. Populate `leftPQ` by adding the first `candidates` workers (`costs[0]` to `costs[candidates-1]`). Update `left` to `candidates`.
4. Populate `rightPQ` by adding the last `candidates` workers, but only if their index is not already covered by the left pool (i.e., index `i >= left`). Update `right` accordingly.
5. Loop `k` times:
    a. Peek at the top elements of both PQs: `leftCandidate` and `rightCandidate`.
    b. If one queue is empty, choose the candidate from the non-empty one.
    c. If both are non-empty, compare them. If `leftCandidate.cost <= rightCandidate.cost`, choose the left one. Otherwise, choose the right one. (The tie-breaking by index is implicitly handled if costs are equal, as the left candidate will always have a smaller index).
    d. Add the chosen candidate's cost to `totalCost` and `poll()` from the corresponding PQ.
    e. If the `left` and `right` pointers have not crossed (`left <= right`):
        i. If the left candidate was chosen, `offer` the worker at `costs[left]` to `leftPQ` and increment `left`.
        ii. If the right candidate was chosen, `offer` the worker at `costs[right]` to `rightPQ` and decrement `right`.
6. Return `totalCost`.

# Solutions
### Java

```java
class Solution {
public
  long totalCost(int[] costs, int k, int candidates) {
    PriorityQueue<int[]> q = new PriorityQueue<>((a, b)->{
      if (a[0] == b[0]) {
        return a[1] - b[1];
      }
      return a[0] - b[0];
    });
    int n = costs.length;
    int i = candidates - 1, j = n - candidates;
    for (int h = 0; h < candidates; ++h) {
      q.offer(new int[]{costs[h], h});
    }
    for (int h = n - candidates; h < n; ++h) {
      if (h > i) {
        q.offer(new int[]{costs[h], h});
      }
    }
    long ans = 0;
    while (k-- > 0) {
      var e = q.poll();
      int c = e[0], x = e[1];
      ans += c;
      if (x <= i) {
        if (++i < j) {
          q.offer(new int[]{costs[i], i});
        }
      }
      if (x >= j) {
        if (--j > i) {
          q.offer(new int[]{costs[j], j});
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
using pii = pair < int , int > ; class Solution { public: long long totalCost ( vector < int >& costs , int k , int candidates ) { priority_queue < pii , vector < pii > , greater < pii >> q ; int n = costs . size (); int i = candidates - 1 , j = n - candidates ; for ( int h = 0 ; h < candidates ; ++ h ) q . push ({ costs [ h ], h }); for ( int h = n - candidates ; h < n ; ++ h ) if ( h > i ) q . push ({ costs [ h ], h }); long long ans = 0 ; while ( k -- ) { auto [ c , x ] = q . top (); q . pop (); ans += c ; if ( x <= i ) { if ( ++ i < j ) { q . push ({ costs [ i ], i }); } } if ( x >= j ) { if ( -- j > i ) { q . push ({ costs [ j ], j }); } } } return ans ; } };
```

### Python

```python
class Solution:
    def totalCost(self, costs: List[int], k: int, candidates: int) -> int: q = [] n = len(costs) i, j = candidates - 1, n - candidates for h in range(candidates): q . append((costs[h], h)) for h in range(n - candidates, n): if h > i: q . append((costs[h], h)) heapify(q) ans = 0 for _ in range(k): c, x = heappop(q) ans += c if x <= i: i += 1 if i < j: heappush(q, (costs[i], i)) if x >= j: j -= 1 if i < j: heappush(q, (costs[j], j)) return ans

```