Total cost to hire k workers

Array Two Pointers Heap (Priority Queue) Simulation

43.5% acceptance

Feb 25, 2026

2075

754

You are given a 0-indexed integer array costs where costs[i] is the cost of h iring the ith worker. * You are also given two integers k and candidates. We want to hire exactly k w orkers 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 th e 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 h iring 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.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn total_cost(costs: Vec<i32>, k: i32, candidates: i32) -> i64 {
    use std::collections::BinaryHeap;
    use std::cmp::Reverse;
    let n = costs.len();
    let c = candidates as usize;
    let mut heap: BinaryHeap<Reverse<(i32, usize)>> = BinaryHeap::new();
    let mut lo = 0usize;
    let mut hi = n;
    // add first c from left
    for _ in 0..c {
      if lo < hi {
        heap.push(Reverse((costs[lo], lo)));
        lo += 1;
      }
    }
    // add last c from right (non-overlapping with lo)
    for _ in 0..c {
      if hi > lo {
        hi -= 1;
        heap.push(Reverse((costs[hi], hi)));
      }
    }
    let mut ans = 0i64;
    for _ in 0..k {
      let Reverse((cost, idx)) = heap.pop().unwrap();
      ans += cost as i64;
      if idx < lo {
        // came from left side, expand right
        if lo < hi {
          heap.push(Reverse((costs[lo], lo)));
          lo += 1;
        }
      } else {
        // came from right side, expand left
        if hi > lo {
          hi -= 1;
          heap.push(Reverse((costs[hi], hi)));
        }
      }
    }
    ans
  }
}