2141. Maximum Running Time of N Computers Hard

1/**
2 * [2141] Maximum Running Time of N Computers
3 *
4 * You have n computers. You are given the integer n and a 0-indexed integer array batteries where the i^th battery can run a computer for batteries[i] minutes. You are interested in running all n computers simultaneously using the given batteries.
5 * Initially, you can insert at most one battery into each computer. After that and at any integer time moment, you can remove a battery from a computer and insert another battery any number of times. The inserted battery can be a totally new battery or a battery from another computer. You may assume that the removing and inserting processes take no time.
6 * Note that the batteries cannot be recharged.
7 * Return the maximum number of minutes you can run all the n computers simultaneously.
8 *  
9 * Example 1:
10 * <img alt="" src="https://assets.leetcode.com/uploads/2022/01/06/example1-fit.png" style="width: 762px; height: 150px;" />
11 * Input: n = 2, batteries = [3,3,3]
12 * Output: 4
13 * Explanation: 
14 * Initially, insert battery 0 into the first computer and battery 1 into the second computer.
15 * After two minutes, remove battery 1 from the second computer and insert battery 2 instead. Note that battery 1 can still run for one minute.
16 * At the end of the third minute, battery 0 is drained, and you need to remove it from the first computer and insert battery 1 instead.
17 * By the end of the fourth minute, battery 1 is also drained, and the first computer is no longer running.
18 * We can run the two computers simultaneously for at most 4 minutes, so we return 4.
19 * 
20 * Example 2:
21 * <img alt="" src="https://assets.leetcode.com/uploads/2022/01/06/example2.png" style="width: 629px; height: 150px;" />
22 * Input: n = 2, batteries = [1,1,1,1]
23 * Output: 2
24 * Explanation: 
25 * Initially, insert battery 0 into the first computer and battery 2 into the second computer. 
26 * After one minute, battery 0 and battery 2 are drained so you need to remove them and insert battery 1 into the first computer and battery 3 into the second computer. 
27 * After another minute, battery 1 and battery 3 are also drained so the first and second computers are no longer running.
28 * We can run the two computers simultaneously for at most 2 minutes, so we return 2.
29 * 
30 *  
31 * Constraints:
32 * 
33 * 	1 <= n <= batteries.length <= 10^5
34 * 	1 <= batteries[i] <= 10^9
35 * 
36 */
37pub struct Solution {}
38
39// problem: https://leetcode.com/problems/maximum-running-time-of-n-computers/
40// discuss: https://leetcode.com/problems/maximum-running-time-of-n-computers/discuss/?currentPage=1&orderBy=most_votes&query=
41
42// submission codes start here
43
44impl Solution {
45    pub fn max_run_time(n: i32, batteries: Vec<i32>) -> i64 {
46        
47    }
48}
49
50// submission codes end
51
52#[cfg(test)]
53mod tests {
54    use super::*;
55
56    #[test]
57    fn test_2141() {
58    }
59}
60