Maximum Running Time of N Computers

Hard

Asked by:

45 views

Topics:

Binary SearchArraysGreedy Algorithms

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.

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 <= 10⁵
1 <= batteries[i] <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the upper bounds for `n` (number of computers) and the values within the `batteries` array?
Can the `batteries` array contain zero values?
Is `n` always less than or equal to the number of batteries available (i.e., the length of the `batteries` array)?
If it's impossible to run all `n` computers simultaneously, what should the function return (e.g., 0)?
Are the battery running times integers or can they be floating-point numbers?

Brute Force Solution

Approach

To find the maximum running time, we will explore every possible amount of time we can run the computers. We will check if each possible time is achievable by trying out all combinations of batteries.

Here's how the algorithm would work step-by-step:

Start with the smallest possible running time (e.g., 1 minute) and gradually increase it.
For each possible running time, check if it's feasible to run all the computers for that long.
To check if a running time is feasible, consider all the different ways to assign batteries to the computers.
For each assignment, calculate how much total battery power is used.
If the total battery power used in an assignment is less than or equal to the total power of the available batteries, then that running time is possible.
If a running time is possible, save it. If not, discard it.
Continue checking increasing running times until you find a time that's too long (not possible).
The last saved running time that was possible is the maximum running time.

Code Implementation

def max_running_time_brute_force(num_computers, batteries):
    total_battery_power = sum(batteries)
    
    # Binary search for the maximum possible running time
    low_time = 1
    high_time = total_battery_power // num_computers
    max_possible_time = 0
    
    while low_time <= high_time:
        mid_time = (low_time + high_time) // 2
        
        # Check if the mid_time is a possible running time
        possible = is_running_time_possible(num_computers, batteries, mid_time)
        
        # If the mid_time is possible, try a higher time
        if possible:
            max_possible_time = mid_time
            low_time = mid_time + 1
        # If the mid_time is not possible, try a lower time
        else:
            high_time = mid_time - 1
            
    return max_possible_time

def is_running_time_possible(num_computers, batteries, running_time):
    batteries.sort(reverse=True)
    
    # We only need to check the 'n' largest batteries
    usable_batteries = batteries[:num_computers]
    
    total_power = 0
    for battery in usable_batteries:
        total_power += min(battery, running_time)

    #Checking if the batteries can actually provide the power for the running time
    return total_power >= num_computers * running_time

Big(O) Analysis

Time Complexity

O(b^n * n!) – The algorithm iterates through possible running times in a loop. For each possible running time, it checks all possible combinations of assigning the b batteries to the n computers. There are n! ways to assign batteries if each computer must have one, but since we are picking a subset of batteries (all possible combinations of batteries), this is closer to b^n combinations. For each of the b^n combinations, we calculate the total battery power used, which takes O(n) time. Thus, the complexity becomes approximately O(b^n * n!).

Space Complexity

O(1) – The described algorithm iterates through possible running times and checks the feasibility of each. However, the plain English explanation suggests trying 'all combinations of batteries' which implies exploring different assignments, and calculating 'total battery power used'. It does not mention specific auxiliary data structures like lists, hash maps, or arrays to store these combinations or assignments. Only a few variables seem to be needed to keep track of the total battery power used in an assignment and compare it with the total battery power of the batteries. Therefore, the auxiliary space used is constant regardless of the number of computers N, and the amount of batteries. Thus, the space complexity is O(1).

Optimal Solution

Approach

The most efficient way to solve this problem is by figuring out the highest possible running time and then checking if we can actually achieve it. We do this by focusing on using the smallest batteries effectively to reach that target time.

Here's how the algorithm would work step-by-step:

First, calculate the total energy all the batteries have combined.
Next, think about what the absolute maximum possible running time could be if we could use all the batteries. This is the total energy divided by the number of computers.
Sort the batteries from smallest to largest.
Check if that maximum running time is even possible. Start by checking if the biggest battery on its own could run longer than that max time. If it can, we can only use a part of the battery that gives us the max run time and that battery is effectively capped to the value of the max run time, otherwise we use the entire battery.
Go through the sorted list of batteries from the smallest batteries upward. For each battery, check if we can fully use its energy to reach the max possible running time for all computers. If we can't, it means our initial maximum running time was too optimistic.
If we find that we can't use all the batteries to achieve our initial maximum running time, reduce the number of computers, effectively increasing the running time required from each battery. Check if you can achieve the current adjusted running time with the batteries. Continue this process until you find the true achievable maximum running time.
The last remaining number after these adjustments will be the longest time we can run all the computers.

Code Implementation

def max_running_time(number_of_computers, battery_power):
    total_battery_power = sum(battery_power)
    max_possible_running_time = total_battery_power // number_of_computers

    battery_power.sort()

    # We must assess if the batteries realistically support this time
    while battery_power and battery_power[-1] > max_possible_running_time:
        total_battery_power -= battery_power.pop()
        number_of_computers -= 1
        # Recalculate the max possible running time based on updated parameters
        max_possible_running_time = total_battery_power // number_of_computers

    # Batteries can achieve this target
    return max_possible_running_time

Big(O) Analysis

Time Complexity

O(n log n) – The algorithm first calculates the total energy, which takes O(n) time where n is the number of batteries. Sorting the batteries takes O(n log n) time. The subsequent steps involve iterating through the sorted batteries. Although there may be adjustments to the target running time, the primary operations within the loop are comparisons and basic arithmetic which take constant time, and this loop iterates at most n times. Thus, the dominant operation is sorting, making the overall time complexity O(n log n).

Space Complexity

O(1) – The primary auxiliary space usage comes from sorting the batteries. However, depending on the sorting algorithm used, this operation could be done in place, or require additional space. Assuming the sorting can be done in place or if the problem statement does not include the sorting step, the provided steps use a few variables to store intermediate calculations like total energy, maximum running time, and a single loop counter. The space required for these variables remains constant irrespective of the number of batteries (N). Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
batteries is null or empty	Return 0 if batteries is null or empty as no running time is possible.
n is 0	Return 0 if n is 0 since there are no computers to run.
batteries array size is less than n	Return 0 as there are not enough batteries to power all computers.
All battery values are 0	Return 0 as no computer can run with batteries having 0 capacity.
Large battery values leading to potential integer overflow when calculating sum	Use long data type to store intermediate sums and results to avoid overflow.
n is very large, close to the batteries array size	The binary search should still work efficiently as it narrows the search range quickly, without requiring special adjustments for nearly equal sizes.
batteries array contains duplicate values	Duplicates are handled correctly by the algorithm as the binary search finds the maximum possible running time regardless of duplicate battery values.
batteries array contains a single very large battery and n is a small number	The algorithm correctly identifies the maximum running time as the average of available power divided across the computers.

batteries is null or empty

How to Handle:

Return 0 if batteries is null or empty as no running time is possible.

n is 0

How to Handle:

Return 0 if n is 0 since there are no computers to run.

batteries array size is less than n

How to Handle:

Return 0 as there are not enough batteries to power all computers.

All battery values are 0

How to Handle:

Return 0 as no computer can run with batteries having 0 capacity.

Large battery values leading to potential integer overflow when calculating sum

How to Handle:

Use long data type to store intermediate sums and results to avoid overflow.

n is very large, close to the batteries array size

How to Handle:

The binary search should still work efficiently as it narrows the search range quickly, without requiring special adjustments for nearly equal sizes.

batteries array contains duplicate values

How to Handle:

Duplicates are handled correctly by the algorithm as the binary search finds the maximum possible running time regardless of duplicate battery values.

batteries array contains a single very large battery and n is a small number

How to Handle:

The algorithm correctly identifies the maximum running time as the average of available power divided across the computers.