2141. Maximum Running Time of N Computers Solution

The problem

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⁹

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.

Python

def maxRunTime(n, batteries):
    totalSum = sum(batteries)
    left, right = 0, totalSum // n
    
    def canRunSimultaneously(t):
        timeSum = sum(min(battery, t) for battery in batteries)
        return timeSum >= t * n
    
    while left < right:
        mid = right - (right - left) // 2
        if canRunSimultaneously(mid):
            left = mid
        else:
            right = mid - 1

    return left

Java

import java.util.*;

class Solution {
    public long maxRunTime(int n, int[] batteries) {
        long totalSum = 0;
        for (int battery : batteries) {
            totalSum += battery;
        }
        long left = 0, right = totalSum / n;
        while (left < right) {
            long mid = right - (right - left) / 2;
            if (canRunSimultaneously(mid, batteries, n)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    private boolean canRunSimultaneously(long t, int[] batteries, int n) {
        long timeSum = 0;
        for (int battery : batteries) {
            timeSum += Math.min(battery, t);
        }
        return timeSum >= t * n;
    }
}

C++

#include <vector>
#include <algorithm>

bool canRunSimultaneously(long long t, const std::vector<int>& batteries, int n) {
    long long timeSum = 0;
    for (long long battery : batteries) {
        timeSum += (battery < t ? battery : t);
    }
    return timeSum >= t * n;
}

long long maxRunTime(int n, std::vector<int>& batteries) {
    long long totalSum = 0;
    for (int battery : batteries) {
        totalSum += battery;
    }
    long long left = 0, right = totalSum / n;
    while (left < right) {
        long long mid = right - (right - left) / 2;
        if (canRunSimultaneously(mid, batteries, n)) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    return left;
}

JavaScript

function maxRunTime(n, batteries) {
    let totalSum = batteries.reduce((a, b) => a + b, 0);
    let left = 0, right = Math.floor(totalSum / n);

    const canRunSimultaneously = (t) => {
        let timeSum = batteries.reduce((sum, b) => sum + Math.min(b, t), 0);
        return timeSum >= t * n;
    };

    while (left < right) {
        let mid = right - Math.floor((right - left) / 2);
        if (canRunSimultaneously(mid)) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    return left;
}

#include <stdio.h>
#include <stdbool.h>

bool canRunSimultaneously(long t, long long sum, int n, int* batteries, int batterySize) {
    long long requiredTime = t * n;
    if(sum < requiredTime) return false;
    long long currentTime = 0;
    for(int i = 0; i < batterySize; i++) {
        currentTime += batteries[i] < t ? batteries[i] : t;
        if(currentTime >= requiredTime) return true;
    }
    return currentTime >= requiredTime;
}

long maxRunTime(int n, int* batteries, int batteriesSize){
    long long sum = 0;
    for(int i = 0; i < batteriesSize; i++) {
        sum += batteries[i];
    }
    long left = 0, right = sum / n;
    while(left < right) {
        long mid = right - (right - left) / 2;
        if(canRunSimultaneously(mid, sum, n, batteries, batteriesSize)) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    return left;
}

public class Solution {
    public long MaxRunTime(int n, int[] batteries) {
        long totalSum = 0;
        foreach (var battery in batteries) {
            totalSum += battery;
        }
        long left = 0, right = totalSum / n;
        while (left < right) {
            long mid = right - (right - left) / 2;
            if (CanRunSimultaneously(mid, batteries, n)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    private bool CanRunSimultaneously(long t, int[] batteries, int n) {
        long timeSum = 0;
        foreach (var battery in batteries) {
            timeSum += Math.Min(battery, t);
        }
        return timeSum >= t * n;
    }
}

The Python solution uses a concise and functional approach with a nested helper function canRunSimultaneously() within maxRunTime(). This function uses binary search to find the optimal time, employing the sum() and min() functions to compute available time each computer can be supported.

Complexity

Time Complexity: O(m log(sum/n))

Space Complexity: O(1)

Try this approach in the editor

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.

Python

def maxRunTime(n, batteries):
    batteries.sort(reverse=True)
    totalSum = sum(batteries)
    i = 0
    while totalSum // n < batteries[i]:
        totalSum -= batteries[i]
        i += 1
        n -= 1
    return totalSum // n

Java

import java.util.*;

class Solution {
    public long maxRunTime(int n, int[] batteries) {
        Arrays.sort(batteries);
        int length = batteries.length;
        long totalSum = 0;
        for (int battery : batteries) {
            totalSum += battery;
        }
        int i = length - 1;
        while ((totalSum / n) < batteries[i]) {
            totalSum -= batteries[i];
            i--;
            n--;
        }
        return totalSum / n;
    }
}

C++

#include <vector>
#include <algorithm>

long long maxRunTime(int n, std::vector<int>& batteries) {
    std::sort(batteries.begin(), batteries.end(), std::greater<int>());
    long long totalSum = 0;
    for (int battery : batteries) {
        totalSum += battery;
    }
    int i = 0;
    while (totalSum / n < batteries[i]) {
        totalSum -= batteries[i];
        i++;
        n--;
    }
    return totalSum / n;
}

JavaScript

function maxRunTime(n, batteries) {
    batteries.sort((a, b) => b - a);
    let totalSum = batteries.reduce((sum, battery) => sum + battery, 0);
    let i = 0;
    while (Math.floor(totalSum / n) < batteries[i]) {
        totalSum -= batteries[i];
        n--;
        i++;
    }
    return Math.floor(totalSum / n);
}

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *a, const void *b) {
    return *(int*)b - *(int*)a;
}

long maxRunTime(int n, int* batteries, int batteriesSize) {
    qsort(batteries, batteriesSize, sizeof(int), cmp);
    long long totalSum = 0;
    for (int i = 0; i < batteriesSize; i++) {
        totalSum += batteries[i];
    }
    int i = 0;
    while (totalSum / n < batteries[i]) {
        totalSum -= batteries[i];
        i++;
        n--;
    }
    return totalSum / n;
}

using System;

public class Solution {
    public long MaxRunTime(int n, int[] batteries) {
        Array.Sort(batteries, (a, b) => b.CompareTo(a));
        long totalSum = 0;
        foreach (var battery in batteries) {
            totalSum += battery;
        }
        int i = 0;
        while (totalSum / n < batteries[i]) {
            totalSum -= batteries[i];
            i++;
            n--;
        }
        return totalSum / n;
    }
}

In this Python approach, the batteries are sorted in decreasing order. The objective is to evenly distribute the total sum of battery runtimes. The while loop readjusts totalSum and active n as necessary, observing whether the divided times exceed the runtime of sorted battery values at each iteration.

Complexity

Time Complexity: O(m log m)

Space Complexity: O(1)

Try this approach in the editor

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).

TypeScript

function maxRunTime(n: number, batteries: number[]): number {
    let l = 0n;
    let r = 0n;
    for (const x of batteries) {
        r += BigInt(x);
    }
    while (l < r) {
        const mid = (l + r + 1n) >> 1n;
        let s = 0n;
        for (const x of batteries) {
            s += BigInt(Math.min(x, Number(mid)));
        }
        if (s >= mid * BigInt(n)) {
            l = mid;
        } else {
            r = mid - 1n;
        }
    }
    return Number(l);
}

func maxRunTime(n int, batteries []int) int64 {
	l, r := 0, 0
	for _, x := range batteries {
		r += x
	}
	for l < r {
		mid := (l + r + 1) >> 1
		s := 0
		for _, x := range batteries {
			s += min(x, mid)
		}
		if s >= n*mid {
			l = mid
		} else {
			r = mid - 1
		}
	}
	return int64(l)
}

Rust

impl Solution {
    pub fn max_run_time(n: i32, batteries: Vec<i32>) -> i64 {
        let n = n as i64;
        let mut l: i64 = 0;
        let mut r: i64 = batteries.iter().map(|&x| x as i64).sum();

        while l < r {
            let mid = (l + r + 1) >> 1;
            let mut s: i64 = 0;

            for &x in &batteries {
                let v = x as i64;
                s += if v < mid { v } else { mid };
            }

            if s >= n * mid {
                l = mid;
            } else {
                r = mid - 1;
            }
        }

        l
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Binary Search on Maximum Time	Time Complexity: O(m log(sum/n)) Space Complexity: O(1)
Greedy Approach with Sorting	Time Complexity: O(m log m) Space Complexity: O(1)
Binary Search	–

Approach

Complexity

Binary Search on Maximum Time

Time Complexity: O(m log(sum/n))

Space Complexity: O(1)

Greedy Approach with Sorting

Time Complexity: O(m log m)

Space Complexity: O(1)

Binary Search

–

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.

Frequently asked questions

Is Maximum Running Time of N Computers easy or hard?

LeetCode classifies this problem as Hard because it requires recognizing a search-on-answer pattern and designing a correct feasibility check. The implementation itself is not long, but the insight about distributing battery capacity makes it challenging for many candidates.

Maximum Running Time of N Computers Python/Java solution

Both Python and Java implementations typically use binary search on the runtime. The feasibility check iterates through the battery array and sums min(battery, t). If the sum is at least n * t, the runtime is feasible and the search continues to the right.

How to solve Maximum Running Time of N Computers in O(n)?

A strict O(n) algorithm is uncommon because most solutions rely on binary search over the runtime range. However, after sorting batteries once (O(m log m)), the greedy energy distribution approach computes the final runtime in linear passes. The binary search feasibility check itself is O(m) per iteration.

What is the best approach for Maximum Running Time of N Computers?

Binary search on the answer combined with a greedy feasibility check is the most widely used approach. For a candidate runtime t, compute sum(min(battery, t)) across all batteries and check if it is at least n * t. This runs in O(m log S) time where m is the number of batteries and S is the total capacity range.

Is Maximum Running Time of N Computers asked at Google/Amazon/Meta?

This problem represents a common interview pattern involving binary search on the answer and greedy resource allocation. Variants of this style frequently appear in interviews at companies like Google, Amazon, and Meta, especially for senior backend or infrastructure roles.

What data structure is used in Maximum Running Time of N Computers?

The problem mainly uses arrays to store battery capacities. The algorithm relies more on mathematical reasoning, greedy allocation, and binary search rather than complex data structures. Sorting the array is required in the greedy approach.

What is the time complexity of Maximum Running Time of N Computers?

The common binary search solution runs in O(m log S) time, where m is the number of batteries and S is the maximum possible runtime (bounded by total battery capacity divided by n). Each binary search step scans the battery array once. Space complexity is O(1).

Maximum Running Time of N Computers solution and explanation

The problem

Approach overview

Approach 1: Binary Search on Maximum Time

Approach 2: Greedy Approach with Sorting

Approach 3: Binary Search

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Maximum Running Time of N Computers solution and explanation

The problem

Approach overview

Approach 1: Binary Search on Maximum Time

Approach 2: Greedy Approach with Sorting

Approach 3: Binary Search

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems