Maximum Running Time of N Computers - Solution & Explanation
Problem Statement
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] <= 109
Approach Overview
Problem Overview: You have n computers and a list of battery capacities. A computer can run on any battery, and batteries can be swapped between computers at any time. The goal is to compute the maximum number of minutes all n computers can run simultaneously.
Approach 1: Greedy with Sorting (O(m log m) time, O(1) space)
Start by sorting the battery capacities using sorting. If a battery is extremely large compared to others, dedicating it to a single computer wastes potential shared runtime. The greedy idea is to treat total battery energy as a shared pool while gradually eliminating oversized batteries that exceed the average runtime. Compute the total sum of all capacities, then compare the largest battery with sum / n. If the largest battery is bigger than the average share, remove it from the pool and reduce the number of computers considered. Continue until the largest battery fits within the equal distribution. The remaining average sum / n becomes the maximum running time. Sorting makes it easy to process the largest batteries first, and the greedy reasoning works because runtime is limited by how evenly total energy can be distributed.
Approach 2: Binary Search on Maximum Time (O(m log S) time, O(1) space)
This approach treats the runtime as the value to search for using binary search. The key observation: if you guess a runtime t, each battery can contribute at most min(capacity, t) minutes because a single battery cannot power multiple computers simultaneously beyond its capacity. Sum these contributions across all batteries. If the total available minutes is at least n * t, then running all computers for t minutes is feasible.
Binary search between 0 and sum(batteries) / n. For each candidate time, iterate through the array of batteries and accumulate min(battery, t). If the sum meets the requirement, move the search right to try a larger runtime; otherwise move left. This feasibility check forms a classic "search on answer" pattern. The approach combines greedy resource allocation with binary search to efficiently handle large inputs.
Recommended for interviews: The binary search solution is what most interviewers expect. It demonstrates recognition of the "search on answer" pattern and the ability to design a feasibility check using greedy reasoning. The greedy sorting method shows deeper insight into energy distribution and can lead to an elegant constant‑space implementation, but the binary search version is usually easier to reason about under interview pressure.
Approach 1: Binary Search on Maximum Time
We 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:
- Compute the total available battery running time.
- Use binary search on the time interval [0, sum of battery times / n].
- For each mid-point in binary search, check if all computers can run for mid minutes by attempting to divide up the battery running time accordingly.
- Adjust the search range according to whether mid was feasible.
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.
Complexity
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.
Approach 2: Greedy Approach with Sorting
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.
- Sort the batteries in descending order.
- Distribute the battery charge to each computer aiming for an even distribution.
- Revise distribution until longest running time is found.
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.
Complexity
Time Complexity: O(m log m), because of the sorting step.
Space Complexity: O(1), in-place operations on the battery array.
Approach 3: Binary Search
We notice that if we can run n computers simultaneously for t minutes, then we can also run n computers simultaneously for t' \le t minutes, which shows monotonicity. Therefore, we can use the binary search method to find the maximum t.
We define the left boundary of the binary search as l=0 and the right boundary as r=sum_{i=0}^{n-1} batteries[i]. During each binary search iteration, we use a variable mid to represent the current middle value, i.e., mid = (l + r + 1) >> 1. We check if there exists a scheme that allows n computers to run simultaneously for mid minutes. If such a scheme exists, then we update l to mid; otherwise, we update r to mid - 1. Finally, we return l as the answer.
The problem is transformed into how to determine if there exists a scheme that allows n computers to run simultaneously for mid minutes. If a battery can run for more minutes than mid, since the computers run simultaneously for mid minutes and a battery can only power one computer at a time, we can only use this battery for mid minutes. If a battery can run for minutes less than or equal to mid, we can use all the power of this battery. Therefore, we calculate the total minutes s that all batteries can power, and if s \ge n times mid, then we can make n computers run simultaneously for mid minutes.
The time complexity is O(n times log M), where M is the total power of all batteries, and the space complexity is O(1).
Complexity Comparison
| 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. |
| Binary Search | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Sorting | O(m log m) | O(1) | When you want a direct mathematical distribution approach and are comfortable reasoning about removing oversized batteries. |
| Binary Search on Maximum Time | O(m log S) | O(1) | General case and most common interview solution using feasibility check with binary search. |
Video Solution
Maximum Running Time of N Computers | Detailed Deep Dive | Dry Run | Leetcode 2141 | MIK • codestorywithMIK • 14,577 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximum Running Time of N Computers easy or hard?
Maximum Running Time of N Computers Python/Java solution
How to solve Maximum Running Time of N Computers in O(n)?
What is the best approach for Maximum Running Time of N Computers?
Is Maximum Running Time of N Computers asked at Google/Amazon/Meta?
What data structure is used in Maximum Running Time of N Computers?
What is the time complexity of Maximum Running Time of N Computers?
Ready to solve this problem?
Practice Maximum Running Time of N Computers with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor