Minimum Data Center Battery Capacity

Overview

The problem asks for the minimum starting battery capacity such that the battery level remains strictly greater than 0 after processing a series of tasks. We are given a usage array and a maxRecovery value that can be used exactly once to reduce the cost of a single task by min(usage[i], maxRecovery).

The intuition is straightforward: to minimize the required starting capacity, we must maximize the benefit of our single backup generator use. Since the generator reduces the total energy drained from the battery, using it on the task that yields the largest reduction will result in the smallest possible starting capacity.

Brute Force

A brute force approach would involve simulating the battery consumption for every possible choice of which task to use the generator on. For an array of size $N$, we would perform $N$ simulations. Each simulation checks the total energy required and determines the starting capacity needed to stay above zero throughout that specific sequence.

def minStartingCapacity(usage: list[int], maxRecovery: int) -> int:
    n = len(usage)
    min_capacity_needed = float('inf')
    
    # Try using the generator on each task i
    for i in range(n):
        current_battery = 0
        lowest_point = 0
        
        for j in range(n):
            cost = usage[j]
            if i == j:
                cost -= min(usage[j], maxRecovery)
            
            current_battery -= cost
            lowest_point = min(lowest_point, current_battery)
        
        # To keep battery > 0, we need starting + lowest_point > 0
        # starting > -lowest_point -> starting = 1 - lowest_point
        needed = 1 - lowest_point
        min_capacity_needed = min(min_capacity_needed, max(1, needed))
            
    return int(min_capacity_needed)

• Time complexity: O(N²) — We iterate through the list of tasks $N$ times, performing a full simulation of length $N$ for each choice.
• Space complexity: O(1) — We only store a few variables to track the battery level and minimum capacity.

Optimal Approach

Since the tasks are processed sequentially and the generator only affects the cost of a single task, we can observe that the total energy consumed is the only factor determining the minimum starting capacity (because costs are always non-negative).

To minimize the starting capacity, we simply need to maximize the reduction provided by the generator. The reduction for any task $i$ is min(usage[i], maxRecovery). We find the maximum possible reduction across all tasks, subtract it from the total sum of usage, and then add 1 to ensure the battery level stays strictly above 0.

def minStartingCapacity(usage: list[int], maxRecovery: int) -> int:
    total_usage = sum(usage)
    
    # Find the maximum possible reduction from the generator
    max_reduction = 0
    for cost in usage:
        reduction = min(cost, maxRecovery)
        if reduction > max_reduction:
            max_reduction = reduction
            
    # Minimum capacity = (Total Cost - Max Reduction) + 1
    return (total_usage - max_reduction) + 1

• Time complexity: O(N) — We perform a single pass to calculate the sum and another (or the same) pass to find the maximum reduction.
• Space complexity: O(1) — We only use a constant amount of extra space for the total_usage and max_reduction variables.

Why this works

In many "minimum starting value" problems, you have to worry about the battery dipping below zero at intermediate steps. However, because all costs in this problem are positive (or zero after the generator is applied), the battery level is monotonically decreasing. Therefore, the lowest battery level will always occur at the very end of the sequence. If the battery is above 0 after the final task, it was guaranteed to be above 0 for all previous tasks.

Fast