Maximum Running Time of N Computers

Hard
835.

Maximum Running Time of N Computers

Maximum Running Time of N Computers is a hard coding problem on arrays, sorting and greedy, asked in Amazon, Google and Intuit interviews.

You want to run n computers simultaneously. Battery i can power one computer for batteries[i] minutes.

At any integer minute you may swap batteries between computers, as often as you like, but a battery powers at most one computer at a time. Return the maximum number of minutes all n computers can run together.

Example 1

Input
n = 2, batteries = [3,3,3]
Output
4
Explanation
Run two batteries for 2 minutes, then rotate the third in.

Example 2

Input
n = 2, batteries = [1,1,1,1]
Output
2

Example 3

Input
n = 3, batteries = [10,10,3,5]
Output
8
Explanation
Three computers for 8 minutes need 24 battery-minutes, and capping each battery at 8 supplies exactly 8+8+3+5.

Constraints

  • 1 <= n <= batteries.length <= 1000
  • 1 <= batteries[i] <= 1000000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[]} batteries
 * @return {number}
 */
var maxRunTime = function(n, batteries) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Running Time of N Computers — Problem & Solution

Maximum Running Time of N Computers solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Maximum Running Time of N Computers is a hard coding problem on arrays, sorting and greedy, asked in Amazon, Google and Intuit interviews.

Problem statement

You want to run n computers simultaneously. Battery i can power one computer for batteries[i] minutes.

At any integer minute you may swap batteries between computers, as often as you like, but a battery powers at most one computer at a time. Return the maximum number of minutes all n computers can run together.

Example 1

Input: n = 2, batteries = [3,3,3]
Output: 4
Explanation: Run two batteries for 2 minutes, then rotate the third in.

Example 2

Input: n = 2, batteries = [1,1,1,1]
Output: 2

Example 3

Input: n = 3, batteries = [10,10,3,5]
Output: 8
Explanation: Three computers for 8 minutes need 24 battery-minutes, and capping each battery at 8 supplies exactly 8+8+3+5.

Constraints

  • 1 <= n <= batteries.length <= 1000
  • 1 <= batteries[i] <= 1000000

Hints for Maximum Running Time of N Computers

  1. Hint 1

    If running for t minutes is possible, so is any shorter time — the feasibility is monotone.

  2. Hint 2

    A battery can contribute at most t minutes towards a target of t, however it is swapped.

  3. Hint 3

    So t works exactly when sum(min(batteries[i], t)) >= t · n.

How to solve Maximum Running Time of N Computers

Binary search the running time. For a target t, each battery's usable contribution is capped at t — no single computer can use more than t minutes from one battery — and any allocation meeting the total demand t · n can actually be scheduled.

Approach

  1. Search t over [0, total / n].
  2. can(t): check sum(min(batteries[i], t)) >= t · n.
  3. Take the largest feasible t with the upper-biased midpoint.

Why it works

The cap is necessary because a battery powers one computer at a time, so it can supply at most t of the t minutes. It is also sufficient: with every battery capped at t, the capped amounts can be laid out across the n computers' timelines greedily without any battery overlapping itself — exactly the classic scheduling argument for splittable jobs with a per-job cap. Raising t raises the demand faster than the capped supply, so feasibility is monotone.

Complexity

  • Time — O(m log(total / n))
  • Space — O(1)

Pitfalls

  • t · n reaches about 10^9 · 10^3 = 10^12 — the comparison needs 64-bit.
  • Without the min(·, t) cap, one huge battery would appear to power everything.
  • The upper-biased midpoint is needed for a maximise search.

Reference solution

Python

from typing import List

def maxRunTime(n: int, batteries: List[int]) -> int:
    lo, hi = 0, sum(batteries) // n

    def can(t: int) -> bool:
        if t == 0:
            return True
        need = t * n
        total = 0
        for b in batteries:
            total += min(b, t)
            if total >= need:
                return True
        return total >= need

    while lo < hi:
        mid = (lo + hi + 1) // 2
        if can(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo

Java

private static boolean canRun(int n, int[] batteries, long t) {
    if (t == 0) return true;
    long need = t * n;
    long total = 0;
    for (int b : batteries) {
        total += Math.min((long) b, t);
        if (total >= need) return true;
    }
    return total >= need;
}

public static int maxRunTime(int n, int[] batteries) {
    long sum = 0;
    for (int b : batteries) sum += b;
    long lo = 0, hi = sum / n;
    while (lo < hi) {
        long mid = lo + (hi - lo + 1) / 2;
        if (canRun(n, batteries, mid)) lo = mid; else hi = mid - 1;
    }
    return (int) lo;
}

C++

static bool canRun(int n, vector<int>& batteries, long long t) {
    if (t == 0) return true;
    long long need = t * n;
    long long total = 0;
    for (int b : batteries) {
        total += min((long long) b, t);
        if (total >= need) return true;
    }
    return total >= need;
}

int maxRunTime(int n, vector<int>& batteries) {
    long long sum = 0;
    for (int b : batteries) sum += b;
    long long lo = 0, hi = sum / n;
    while (lo < hi) {
        long long mid = lo + (hi - lo + 1) / 2;
        if (canRun(n, batteries, mid)) lo = mid; else hi = mid - 1;
    }
    return (int) lo;
}

JavaScript

var maxRunTime = function(n, batteries) {
    var total = 0, i;
    for (i = 0; i < batteries.length; i++) total += batteries[i];
    var can = function(t) {
        if (t === 0) return true;
        var sum = 0, need = t * n;
        for (var j = 0; j < batteries.length; j++) {
            sum += Math.min(batteries[j], t);
            if (sum >= need) return true;
        }
        return sum >= need;
    };
    var lo = 0, hi = Math.floor(total / n);
    while (lo < hi) {
        var mid = Math.ceil((lo + hi) / 2);
        if (can(mid)) lo = mid; else hi = mid - 1;
    }
    return lo;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms