You have n computers. You are given the integer n and a 0-indexed integer array batteries where the ith battery can run a computer for batteries[i] minutes. You are interested in running all n computers simultaneously using the given batteries.
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.
Note that the batteries cannot be recharged.
Return the maximum number of minutes you can run all the n computers simultaneously.
Example 1:
Input: n = 2, batteries = [3,3,3] Output: 4 Explanation: Initially, insert battery 0 into the first computer and battery 1 into the second computer. 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. 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. By the end of the fourth minute, battery 1 is also drained, and the first computer is no longer running. We can run the two computers simultaneously for at most 4 minutes, so we return 4.
Example 2:
Input: n = 2, batteries = [1,1,1,1] Output: 2 Explanation: Initially, insert battery 0 into the first computer and battery 2 into the second computer. 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. After another minute, battery 1 and battery 3 are also drained so the first and second computers are no longer running. We can run the two computers simultaneously for at most 2 minutes, so we return 2.
Constraints:
1 <= n <= batteries.length <= 1051 <= batteries[i] <= 109We can use binary search to determine the maximum possible time all computers can run simultaneously. The key observation is that if it's possible to run the computers for t minutes, it's also possible to run them for any time less than t. Similarly, if you cannot run them for t minutes, you cannot for any time greater than t. Here's how we can implement this:
The function maxRunTime implements a binary search to find the maximal possible minutes for which all computers can run simultaneously. The helper function canRunSimultaneously checks if the computers can run for t minutes by distributing available battery time. The binary search tweaks the possible time around the midpoint to find the maximum possible time.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m log(max_time)), where m is the number of batteries.
Space Complexity: O(1), as no extra space proportional to input size is used.
A straightforward approach is sorting the batteries by their available time and then using a greedy method to allocate the longest available running time to any computer that can accommodate it. The goal is to utilize batteries to maximize the running time in descending order until we've depleted either the batteries or optimized distributions.
The solution sorts battery times in descending order using qsort() and then checks where the median division (totalSum divided by n) matches or is exceeded by the battery times. It deducts the unusable surplus battery times from totalSum and decrements n accordingly, distributing the highest possible running time.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m log m), because of the sorting step.
Space Complexity: O(1), in-place operations on the battery array.
| Approach | Complexity |
|---|---|
| Binary Search on Maximum Time | Time Complexity: O(m log(max_time)), where m is the number of batteries. Space Complexity: O(1), as no extra space proportional to input size is used. |
| Greedy Approach with Sorting | Time Complexity: O(m log m), because of the sorting step. Space Complexity: O(1), in-place operations on the battery array. |
Maximum Running Time of N Computers II Binary Search II Leetcode 2141 • Aryan Mittal • 5,280 views views
Watch 9 more video solutions →Practice Maximum Running Time of N Computers with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor