2462. Total Cost to Hire K Workers Medium

1/**
2 * [2462] Total Cost to Hire K Workers
3 *
4 * You are given a 0-indexed integer array costs where costs[i] is the cost of hiring the i^th worker.
5 * You are also given two integers k and candidates. We want to hire exactly k workers according to the following rules:
6 * 
7 * 	You will run k sessions and hire exactly one worker in each session.
8 * 	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.
9 * 	
10 * 		For example, if costs = [3,2,7,7,1,2] and candidates = 2, then in the first hiring session, we will choose the 4^th worker because they have the lowest cost [<u>3,2</u>,7,7,<u>1,2</u>].
11 * 		In the second hiring session, we will choose 1^st worker because they have the same lowest cost as 4^th worker but they have the smallest index [<u>3,2</u>,7,<u>7,2</u>]. Please note that the indexing may be changed in the process.
12 * 	
13 * 	
14 * 	If there are fewer than candidates workers remaining, choose the worker with the lowest cost among them. Break the tie by the smallest index.
15 * 	A worker can only be chosen once.
16 * 
17 * Return the total cost to hire exactly k workers.
18 *  
19 * <strong class="example">Example 1:
20 * 
21 * Input: costs = [17,12,10,2,7,2,11,20,8], k = 3, candidates = 4
22 * Output: 11
23 * Explanation: We hire 3 workers in total. The total cost is initially 0.
24 * - In the first hiring round we choose the worker from [<u>17,12,10,2</u>,7,<u>2,11,20,8</u>]. The lowest cost is 2, and we break the tie by the smallest index, which is 3. The total cost = 0 + 2 = 2.
25 * - In the second hiring round we choose the worker from [<u>17,12,10,7</u>,<u>2,11,20,8</u>]. The lowest cost is 2 (index 4). The total cost = 2 + 2 = 4.
26 * - In the third hiring round we choose the worker from [<u>17,12,10,7,11,20,8</u>]. 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.
27 * The total hiring cost is 11.
28 * 
29 * <strong class="example">Example 2:
30 * 
31 * Input: costs = [1,2,4,1], k = 3, candidates = 3
32 * Output: 4
33 * Explanation: We hire 3 workers in total. The total cost is initially 0.
34 * - In the first hiring round we choose the worker from [<u>1,2,4,1</u>]. 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.
35 * - In the second hiring round we choose the worker from [<u>2,4,1</u>]. The lowest cost is 1 (index 2). The total cost = 1 + 1 = 2.
36 * - In the third hiring round there are less than three candidates. We choose the worker from the remaining workers [<u>2,4</u>]. The lowest cost is 2 (index 0). The total cost = 2 + 2 = 4.
37 * The total hiring cost is 4.
38 * 
39 *  
40 * Constraints:
41 * 
42 * 	1 <= costs.length <= 10^5 
43 * 	1 <= costs[i] <= 10^5
44 * 	1 <= k, candidates <= costs.length
45 * 
46 */
47pub struct Solution {}
48
49// problem: https://leetcode.com/problems/total-cost-to-hire-k-workers/
50// discuss: https://leetcode.com/problems/total-cost-to-hire-k-workers/discuss/?currentPage=1&orderBy=most_votes&query=
51
52// submission codes start here
53
54impl Solution {
55    pub fn total_cost(costs: Vec<i32>, k: i32, candidates: i32) -> i64 {
56        
57    }
58}
59
60// submission codes end
61
62#[cfg(test)]
63mod tests {
64    use super::*;
65
66    #[test]
67    fn test_2462() {
68    }
69}
70