344. Battery Marathon
A lab wants to run computers machines at the same time, and each computer needs one battery at any moment. The array batteries gives the number of minutes each battery lasts. You may swap batteries between computers at any whole minute, any number of times, but a battery can only power one computer at a time and cannot be recharged.
Return the largest number of whole minutes that all computers machines can run simultaneously. A battery that would last longer than the target time is never used for more than that time. The answer can reach about 10^14, so use a 64-bit integer, and do not simulate the swaps minute by minute.
Example 1
- Input:
- computers = 2, batteries = [3,3,3]
- Output:
- 4
- Explanation:
Total energy is 9 minutes; with swapping both computers can run for 4 minutes (two minutes of spare energy are left over).
Example 2
- Input:
- computers = 2, batteries = [1,1,1,1]
- Output:
- 2
- Explanation:
Four batteries of 1 minute give 4 minutes of energy, enough for 2 minutes on 2 computers.
Constraints
1 ≤ computers ≤ batteries.length ≤ 105
1 ≤ batteries[i] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(m log(S / computers))
- Space
- O(1)