Total Cost to Hire K Workers
You are given a 0-indexed integer array costs where costs[i] is the cost of hiring the i^th 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
ksessions and hire exactly one worker in each session. - In each hiring session, choose the worker with the lowest cost from either the first
candidatesworkers or the lastcandidatesworkers. Break ties by the smallest index. - If there are fewer than
candidatesworkers remaining, choose the worker with the lowest cost among them. Break ties 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 = 4Output
11Hiring workers with costs 2, 2, and 7 gives a total cost of 11.
Example 2
Input
costs = [1,2,4,1], k = 3, candidates = 3Output
4Hiring workers with costs 1, 1, and 2 gives a total cost of 4.
Constraints
- 1 <= costs.length <= 10^5
- 1 <= costs[i] <= 10^5
- 1 <= k, candidates <= costs.length