LeetCode 2141 - Maximum Running Time of N Computers

The problem is asking us to determine the maximum number of minutes n computers can run simultaneously using a given set of batteries. Each battery has a fixed amount of energy in minutes, and you can initially assign at most one battery per computer.

leetcodehardarraybinary-searchgreedysorting

LeetCode Problem 2141

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Greedy, Sorting

Solution

Problem Understanding

The problem is asking us to determine the maximum number of minutes n computers can run simultaneously using a given set of batteries. Each battery has a fixed amount of energy in minutes, and you can initially assign at most one battery per computer. After that, you can swap batteries freely between computers at any integer time moment, and each battery can only contribute its total runtime. The goal is to maximize the runtime of all computers running simultaneously.

The input consists of an integer n representing the number of computers and an array batteries where batteries[i] is the duration that the i-th battery can provide. The output is a single integer representing the maximum time all computers can be powered simultaneously.

Constraints show that n can be up to 10^5 and battery capacities up to 10^9. This indicates that any solution that tries all possible permutations of battery allocations or simulates time step by step will be too slow. We also know there will always be at least as many batteries as computers.

Edge cases to consider include:

  1. All batteries are equal.
  2. There are more batteries than computers.
  3. Batteries have large disparities in capacity, e.g., [1,1,1,1000000000].
  4. Only one computer (n = 1) or n equal to the number of batteries.

Approaches

Brute Force Approach:

A naive solution would be to simulate the computers minute by minute, always choosing the largest available battery for each computer when its battery depletes. This guarantees correctness but is far too slow because the total runtime could reach the sum of all batteries, which is up to 10^14 for the given constraints. Iterating minute by minute is not feasible.

Optimal Approach:

The key insight is that we can think in terms of total battery capacity and target runtime per computer. If we assume that all computers run for T minutes, the sum of all batteries must be at least n * T. Batteries with runtime larger than T can simply provide T minutes each, and smaller batteries contribute their full runtime. Using this observation, we can use binary search on T to find the maximum possible runtime.

  1. Set the search range from 1 to sum(batteries) // n.
  2. Check if a candidate runtime mid is achievable by summing min(b, mid) for all batteries and verifying it is at least n * mid.
  3. Adjust the binary search accordingly.

This approach guarantees an answer in logarithmic time relative to the total battery sum.

Approach Time Complexity Space Complexity Notes
Brute Force O(sum(batteries)) O(1) Minute-by-minute simulation of all computers
Optimal O(m log(S)) O(1) Binary search on maximum runtime T, where m = len(batteries) and S = sum(batteries)

Algorithm Walkthrough

  1. Initialize Search Bounds: Calculate the sum of all battery capacities. Set left = 1 and right = sum(batteries) // n.
  2. Binary Search Loop: While left <= right, calculate mid = (left + right) // 2.
  3. Feasibility Check: For each battery, compute min(b, mid) and sum them up. This represents how much the battery contributes toward the target runtime mid.
  4. Adjust Bounds: If the sum is at least n * mid, then mid is achievable. Move left = mid + 1 to try a longer runtime. Otherwise, set right = mid - 1.
  5. Return Result: After binary search ends, right contains the maximum achievable runtime.

Why it works:

The binary search works because the total runtime is monotonically increasing: if T is achievable, any runtime smaller than T is also achievable. The feasibility check ensures that we do not exceed the available total battery capacity.

Python Solution

from typing import List

class Solution:
    def maxRunTime(self, n: int, batteries: List[int]) -> int:
        total = sum(batteries)
        left, right = 1, total // n
        
        def can_run(target: int) -> bool:
            return sum(min(b, target) for b in batteries) >= n * target
        
        while left <= right:
            mid = (left + right) // 2
            if can_run(mid):
                left = mid + 1
            else:
                right = mid - 1
        
        return right

Explanation:

The code calculates the total battery capacity and uses binary search to find the maximum runtime right. The can_run function evaluates if the target runtime is achievable by capping each battery at target minutes and summing the contributions. This efficiently checks feasibility without simulating minute by minute.

Go Solution

func maxRunTime(n int, batteries []int) int64 {
    var total int64
    for _, b := range batteries {
        total += int64(b)
    }
    
    left, right := int64(1), total/int64(n)
    
    canRun := func(target int64) bool {
        var sum int64
        for _, b := range batteries {
            if int64(b) > target {
                sum += target
            } else {
                sum += int64(b)
            }
        }
        return sum >= int64(n)*target
    }
    
    for left <= right {
        mid := (left + right) / 2
        if canRun(mid) {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    
    return right
}

Go Notes:

We use int64 to avoid overflow since sums can exceed 10^14. The binary search logic mirrors the Python version. The main difference is explicit type conversions and handling large sums safely.

Worked Examples

Example 1: n = 2, batteries = [3,3,3]

  1. total = 9, left = 1, right = 4.
  2. Binary search mid = 2. Sum of min(b, 2) = 2+2+2=6 ≥ 4 → feasible → left = 3.
  3. mid = 3. Sum = 3+3+3=9 ≥ 6 → feasible → left = 4.
  4. mid = 4. Sum = 3+3+3=9 < 8 → not feasible → right = 3.
  5. Return right = 4.

Example 2: n = 2, batteries = [1,1,1,1]

  1. total = 4, left = 1, right = 2.
  2. mid = 1. Sum = 1+1+1+1=4 ≥ 2 → feasible → left = 2.
  3. mid = 2. Sum = min(1,2)+min(1,2)+min(1,2)+min(1,2)=4 ≥ 4 → feasible → left = 3.
  4. Return right = 2.

Complexity Analysis

Measure Complexity Explanation
Time O(m log(S)) Binary search over sum range with m = len(batteries) and sum S = sum(batteries). Each check is O(m).
Space O(1) Only variables for binary search and sums are used, no additional structures needed.

The time complexity is efficient even for the upper constraint (m = 10^5) because log(S) is approximately 44 for S ~ 10^14.

Test Cases

# Provided examples
assert Solution().maxRunTime(2, [3,3,3]) == 4  # Example 1
assert Solution().maxRunTime(2, [1,1,1,1]) == 2  # Example 2

# Edge cases
assert Solution().maxRunTime(1, [10]) == 10  # single computer
assert Solution().maxRunTime(3, [3,3,3,3,3]) == 5  # extra battery
assert Solution().maxRunTime(2, [1,2,3,4,5]) == 7  # uneven batteries
assert Solution().maxRunTime(5, [1,1,1,1,1]) == 1  # all minimal
assert Solution().maxRunTime(5, [10**9]*5) == 10**9  # very large batteries
Test Why
[3,3,3], n=2 Verifies correct runtime calculation with moderate batteries
[1,1,1,1], n=2 Tests multiple small batteries can be combined
[10], n=1 Single computer edge case
[3,3,3,3,3], n=3 Extra batteries are available
[1,2,3,4,5], n=2 Uneven battery capacities
[1,1,1,1,1], n=5 Minimum battery capacity
[10**9]*5, n=5 Maximum capacity