Vultr DocsLatest Content

Maximum Running Time of N Computers

Updated on 10 June, 2025
Maximum Running Time of N Computers header image

Problem Statement

In this problem, you have a certain number of computers n and a list of batteries each with a distinct capacity (in minutes). Each battery's capacity is represented by its respective value in the array batteries. Your main goal is to determine how long you can run all n computers simultaneously.

You must begin by assigning one battery to each computer. However, as the simulation progresses, you can interchange these batteries amongst computers or replace a used battery with another. This replacement process is instantaneous and can be performed repeatedly without any time constraint. It's essential to note that batteries are non-rechargeable; once their capacity is exhausted, they cannot be reused.

Your task is to calculate the longest time all computers can run concurrently without any of them shutting down due to a lack of battery power.

Examples

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 <= 105
  • 1 <= batteries[i] <= 109

Approach and Intuition

From the problem statement and examples provided, we can infer a strategy:

  1. Initial setup: At the beginning, distribute the batteries strategically among the computers. An initial interpretation might suggest putting higher battery capacities on computers that have higher needs or splitting them as evenly as possible.

  2. Simulation of operation:

    • Start all computers at the same time with their assigned batteries.
    • As any battery runs out, replace it with another from the pool if available.

  3. Optimization using max operation time: The ideal approach involves finding a balance such that each computer can operate for as long as possible. This often means swapping out batteries between computers to ensure that no computer is idle while there are still batteries available with remaining capacity.

  4. Simulation continues until all batteries are depleted: The operation goes on until it's no longer possible to run all computers simultaneously.

The examples provide clear scenarios where strategic distribution and timely swapping of batteries ensure maximum operational time. These scenarios involve:

  • Calculating ongoing usage to balance out battery lifetimes across computers.
  • Monitoring battery usage in real-time to swiftly replace depleted units.

Therefore, this method leverages the practice of simultaneously balancing battery usage and keeping all computers operational, ensuring a maximized operational period given the constraints and resources available.

Solutions

  • Java
  • Python
java 
class Solution {
    public long maximumRuntime(int count, int[] cells) {
        long totalPower = 0;
        for (int energy : cells)
            totalPower += energy;
        long low = 1, high = totalPower / count;
        
        while (low < high) {
            long mid = high - (high - low) / 2;
            long surplus = 0;
            
            for (int energy : cells)
                surplus += Math.min(energy, mid);

            if (surplus >= (long)(count * mid))
                low = mid;
            else
                high = mid - 1;
        }
        return low;
    }
}

To solve the problem of determining the maximum running time for N computers using a given set of battery cells with specific energy capacities, follow this Java approach. The solution leverages binary search to efficiently find the optimal running time.

*Start by calculating the total power available by summing up the energy from all cells. Initialize binary search boundaries: low starts at 1 and high as the total power divided by the count of computers, ensuring that you take the floor of that division to avoid overestimation.

*Perform a binary search to determine the maximum time (mid) each computer can run so that the sum of the running times does not exceed the available energy:

  1. Calculate the middle point mid by taking the average of the current low and high.
  2. Calculate the total energy that would be consumed if all computers run for mid time. This is done by iterating through each cell and summing up the minimum of the cell's energy and mid.
  3. If the total energy consumed by running the computers for mid time is equal to or greater than the product of the count of computers and mid, adjust low to mid; otherwise, adjust high to mid - 1.

*After exiting the loop, the value in low will be the maximum time that ensures all computers can run simultaneously without running out of power.

This approach makes sure that your solution is both time-efficient and robust, harnessing the power of binary search to cut down on unnecessary computations and directly hone in on the maximum possible running time.

python 
class Solution:
    def maxBatteryUsage(self, devices: int, energy: List[int]) -> int:
        min_energy, max_energy = 1, sum(energy) // devices
        
        while min_energy < max_energy:
            mid = max_energy - (max_energy - min_energy) // 2
            
            surplus = 0
            for power in energy:
                surplus += min(power, mid)
            
            if surplus // devices >= mid:
                min_energy = mid
            else:
                max_energy = mid - 1
        
        return min_energy

The problem at hand involves finding the maximum running time of N computers given their individual energy consumptions. You achieve this by utilizing a binary search technique in Python to ensure efficient performance.

  • Start by initializing the min_energy to 1 and the max_energy to the sum of energies divided by the number of devices.
  • Utilize a while loop to iterate as long as min_energy is less than max_energy.
  • Calculate mid which is an approximation between min_energy and max_energy.
  • Compute the surplus energy by summing up the minimum of each device’s power and mid.
  • If the average surplus energy per device is greater than or equal to mid, update min_energy to mid to seek a potentially higher feasible runtime.
  • If not, reduce max_energy to search for a lower bound, ensuring mid is always feasible.
  • The loop continues until you narrow down the maximum possible running time, which is returned by the function.

This solution ensures a logarithmic time complexity relative to the range of energy values per device, making it highly efficient for large inputs.

Comments

No comments yet.