Maximum Running Time of N Computers

Master this topic with zero to advance depth.

Maximum Running Time of N Computers

You have n computers and batteries. Return the maximum number of minutes you can run all n computers simultaneously.

Hard

Examples

Input: n = 2, batteries = [3,3,3]
Output: 4

Approach 1

Level I: Brute Force

Intuition

The maximum possible time is the average energy: $\\sum(batteries) / n$ .

⏱ $O(M)$💾 $O(1)$

Detailed Dry Run

n=2, batteries=[3,3,3]. Sum=9. Average=4.5. Result: 4.

java

class Solution {
    public long maxRunTime(int n, int[] batteries) {
        long sum = 0;
        for (int b : batteries) sum += b;
        return sum / n;
    }
}

Approach 2

Level III: Optimal (Binary Search on Answer)

Intuition

For a time $T$ , a battery with capacity $B$ can contribute at most $\\min(B, T)$ minutes. Check if $\\sum \\min(B_i, T) \\ge n \\times T$ .

⏱ $O(M \\log(Sum/N))$💾 $O(1)$

Detailed Dry Run

Step	L	R	Mid	Energy	Needed	Decision
1	1	4	3	9	6	L = 3
2	3	4	4	9	8	L = 4
Exit	-	-	-	-	-	Return 4

java

class Solution {
    public long maxRunTime(int n, int[] batteries) {
        long l = 1, r = 0;
        for (int b : batteries) r += b;
        r /= n;
        while (l < r) {
            long m = l + (r - l + 1) / 2;
            if (can(n, batteries, m)) l = m; else r = m - 1;
        }
        return l;
    }
    private boolean can(int n, int[] b, long t) {
        long energy = 0;
        for (int x : b) energy += Math.min((long)x, t);
        return energy >= (long)n * t;
    }
}

← Previous QuestionMinimum Time to Complete Trips

Next Question →Kth Smallest Element in a Sorted Matrix

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.