Total Cost to Hire K Workers
Medium · Heap & Counting · Array · Two Pointers · Heap (Priority Queue) · Simulation
Problem
You are given an array costs, where costs[i] is the cost of hiring worker i, and integers k and candidates. You will hire exactly k workers in k rounds.
In each round, look only at the first candidates workers and the last candidates workers still available, and hire the one with the lowest cost, breaking ties by the smallest index. If fewer than candidates workers remain on either side, consider all remaining workers (a worker is never counted twice). A hired worker leaves the pool.
Return the total cost of hiring all k workers.
Examples
Input: costs = [4,9,1,6,3,5,8], k = 3, candidates = 2 Output: 10
Round 1 sees [4,9] and [5,8] and hires 4; round 2 sees [9,1] and [5,8] and hires 1; round 3 sees [9,6] and [5,8] and hires 5. 4 + 1 + 5 = 10.
Input: costs = [2,2,2,2], k = 2, candidates = 1 Output: 4
Every round is a tie broken by index: workers 0 and then 1.
Input: costs = [1,2,4,1], k = 3, candidates = 3 Output: 4
The two windows overlap and together cover everyone, so the three cheapest are hired: 1 + 1 + 2.
Constraints
- 1 <= len(costs) <= 10^5
- 1 <= costs[i] <= 10^5
- 1 <= k, candidates <= len(costs)
Approaches
- Baseline: scan both windows every round — time O(k · n), space O(n)
Follow-up
Once 2 · candidates >= remaining workers, the windows cover everyone and the rest of the hires are just the cheapest ones left, so sorting what remains would finish faster. The use cases ask for the order of hires and for a budget instead of k.
Related problems
Start free on Cariara · Coding problems · System design studio
