2141. Maximum Running Time of N Computers

HardGreedyArrayBinary SearchSorting
Leetcode Link

Problem Description

You're tasked with powering n computers using a given set of batteries, each with a specific charge duration in minutes. The goal is to make all n computers run simultaneously for the maximum amount of time possible. One battery can be used per computer, and you can switch batteries between the computers at any whole minute without any time penalty. However, the batteries can't be recharged - once a battery's charge is used up, it can't be used again.

Your function's job is to determine the maximum number of minutes that all n computers can be kept running. You're given n and an array batteries, where each element represents the lifetime of a battery.

Intuition

To solve this problem, we have to find a way to balance the battery use across all computers to maximize the time they can run. The intuitive leap is to think of a "load balancing" approach, where we distribute the power supply evenly amongst the computers. Since we're looking for a "fair share" of power that each computer would get, and we aim to maximize this share under the constraints, it seems that binary search could help us zero in on the solution.

We perform a binary search on the range of possible minutes (from 0 to the sum of all battery capacities) to find the maximum time each computer could run. The key intuition is that if it's possible to run all computers for mid minutes, then it's also possible to run them for any amount of time less than mid. Conversely, if it's not possible to run the computers for mid minutes, it won't be possible for any time greater than mid.

In each step of our binary search, we check if it's possible to run all computers for mid minutes. We do this by calculating the sum of min(x, mid) for each battery x in the array batteries. If this sum is at least n * mid, it means that it's possible to distribute the batteries in a way that all computers can run for mid minutes.

If it's possible, we move our search upward (l = mid); otherwise, we move downward (r = mid - 1). When our binary search converges, we've found the maximum time that we can run all computers simultaneously, which will be the value of l.

The solution code implements this binary search strategy to find the optimal run time.

Learn more about Greedy, Binary Search and Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Solution Approach

The implementation of the solution uses binary search as the central algorithm, applying this technique to find the maximum possible running time where all n computers can operate simultaneously using the batteries provided.

We'll break down the key components of the binary search loop from the reference solution:

  1. Initialization of Search Bounds: We set our search bounds for binary search โ€” l (left) is set to 0, and r (right) is set to the sum of all elements in batteries. These represent the minimum and maximum possible running times, respectively.

  2. The Binary Search Loop: Binary search proceeds by repeatedly dividing the search interval in half. If the condition is met, we work with the right half; otherwise, the left half. We continue until l and r converge.

  3. Middle Point Calculation: mid = (l + r + 1) >> 1. Calculating the midpoint of our search range, where >> 1 effectively divides the sum by 2 (bitwise right shift operation which is equivalent to integer division by 2).

  4. Testing if the Midpoint is Feasible: sum(min(x, mid) for x in batteries) >= n * mid. For each battery x, we take the minimum of x and mid since if a battery has more charge than needed (x > mid), we only need up to mid for our current guess. We sum these minimums and compare it to n * mid to verify if we can run all computers for mid minutes: if sum >= n * mid, it's feasible.

  5. Updating Search Bounds: Based on feasibility:

    • If it's feasible to run all computers for mid minutes, then we set l to mid. The +1 in the midpoint calculation ensures we don't get stuck in an infinite loop.
    • If it's not feasible, we set r to mid - 1.

  6. Convergence and Result: When l equals r, the binary search has converged to the maximum amount of time that all computers can run simultaneously, and we return l.

The solution uses a common data structure, a list (or array), to store the durations of batteries. There's no need for advanced data structures since the problem doesn't require any dynamic ordering or storageโ€”just a straightforward computation of the sum under different conditions.

The pattern here is iterative refinement: with each iteration, we get closer to the maximum run time by ruling out half of the remaining possibilities. Binary search is highly efficient for this problem because it cuts down the search space exponentially with each iteration, leading us quickly to the optimal solution.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

A heap is a ...?

Example Walkthrough

Let's illustrate the solution approach using a small example. Suppose we have n = 2 computers and batteries = [3, 7], which means we have 2 batteries that can last for 3 and 7 minutes, respectively. We want to find out the maximum amount of time that both computers can run simultaneously.

  1. Initialization of Search Bounds: We set l = 0 and r = 10 (sum of all battery lifetimes).

  2. The Binary Search Loop begins:

    a. First Iteration: - Calculate mid = (0 + 10 + 1) >> 1 = 5. - Check if mid is feasible: - Computer 1 can use a battery for 3 minutes (as 3 < 5). - Computer 2 can use a battery for 5 minutes (as 7 > 5, but we only need 5). - The total is 3 + 5 = 8, which is less than n * mid (2 * 5 = 10). Not feasible. - Update search bounds: r = mid - 1 = 4.

    b. Second Iteration: - Calculate mid = (0 + 4 + 1) >> 1 = 2. - Check if mid is feasible: - Computer 1 can use a battery for 2 minutes (as 3 > 2). - Computer 2 can use a battery for 2 minutes (as 7 > 2). - The total is 2 + 2 = 4, which equals n * mid (2 * 2 = 4). Feasible. - Update search bounds: l = mid = 2.

    Since l and r have not converged, the search continues.

    c. Third Iteration: - Calculate mid = (2 + 4 + 1) >> 1 = 3. - Check if mid is feasible: - Computer 1 can use a battery for 3 minutes (as 3 >= 3). - Computer 2 can use a battery for 3 minutes (as 7 > 3). - The total is 3 + 3 = 6, which is greater than n * mid (2 * 3 = 6). Feasible. - Update search bounds: l = mid = 3.

    d. Fourth Iteration: - Since l has been updated to 3, 'r' still being 4, so we need to search the upper half [4, 4]: - Calculate mid = (3 + 4 + 1) >> 1 = 4. - Check if mid is feasible: - Computer 1 can use a battery for 3 minutes (as 3 < 4). - Computer 2 can use a battery for 4 minutes (as 7 > 4). - The total is 3 + 4 = 7, which is less than n * mid (2 * 4 = 8). Not feasible. - Since itโ€™s not feasible, we set r = mid - 1 = 3.

  3. Convergence and Result: l and r have converged to 3, meaning the maximum time that both computers can run simultaneously using the given batteries is 3 minutes.

In this example, we've seen how binary search efficiently zeroes in on the maximum time by testing the feasibility at the midpoint of the current search interval and narrowing down based on the results of those tests.

Solution Implementation

1from typing import List
2
3class Solution:
4    def maxRunTime(self, n: int, batteries: List[int]) -> int:
5        # Defines the search space with the minimum possible runtime as `left`
6        # and the maximum as the sum of the capacities of all batteries as `right`
7        left, right = 0, sum(batteries)
8      
9        # Performs binary search to find the maximum runtime
10        while left < right:
11            # Sets `middle` to the average of `left` and `right`
12            # The `+1` ensures that the middle is biased towards the higher end
13            # to prevent infinite loop in case `left` and `right` are consecutive numbers
14            middle = (left + right + 1) // 2
15          
16            # Computes the total run time possible with each battery contributing
17            # either its full capacity or the current `middle` value, which is the
18            # assumed runtime for each UPS if batteries are distributed optimally
19            total_runtime = sum(min(battery_capacity, middle) for battery_capacity in batteries)
20          
21            # If the total achievable runtime is at least `n * middle`, this means
22            # we can guarantee each of the `n` UPS a runtime of `middle`
23            # So we move the `left` boundary to `middle`
24            if total_runtime >= n * middle:
25                left = middle
26            # Otherwise, we have overestimated the maximal achievable runtime,
27            # and so we decrease the `right` boundary
28            else:
29                right = middle - 1
30      
31        # The search ends when `left` and `right` meet, meaning `left` is the maximal
32        # achievable runtime for each UPS
33        return left
34
1class Solution {
2
3    // This method is designed to find the maximum running time for 'n' computers using given batteries
4    public long maxRunTime(int n, int[] batteries) {
5        long left = 0; // Initialize the lower bound of binary search
6        long right = 0; // Initialize the upper bound of binary search
7
8        // Calculate the sum of all the batteries which will be the upper bound
9        for (int battery : batteries) {
10            right += battery;
11        }
12      
13        // Use binary search to find the maximum running time
14        while (left < right) {
15            // Calculate the middle point, leaning towards the higher half
16            long mid = (left + right + 1) >> 1;
17            long sum = 0; // Sum of the minimum of mid and the battery capacities
18
19            // Calculate the sum of the minimum of mid or the battery capacities
20            for (int battery : batteries) {
21                sum += Math.min(mid, battery);
22            }
23
24            // If the sum is sufficient to run 'n' computers for 'mid' amount of time
25            if (sum >= n * mid) {
26                // We have enough capacity, so try a longer time in the next iteration
27                left = mid;
28            } else {
29                // Otherwise, try a shorter time in the next iteration
30                right = mid - 1;
31            }
32        }
33        // Return the maximum running time found through binary search
34        return left;
35    }
36}
37
1class Solution {
2public:
3    long long maxRunTime(int n, vector<int>& batteries) {
4        // Initialize the search space boundary variables.
5        long long left = 0, right = 0;
6      
7        // Calculate the sum of all batteries as the upper bound for binary search.
8        for (int battery : batteries) {
9            right += battery;
10        }
11      
12        // Perform binary search to find the optimal runtime.
13        while (left < right) {
14            // Mid represents a candidate for the maximum runtime.
15            long long mid = (left + right + 1) >> 1;
16          
17            // Sum variable to store the total uptime using the candidate runtime.
18            long long sum = 0;
19          
20            // Calculate total runtime without exceeding individual battery's capacity.
21            for (int battery : batteries) {
22                sum += min(static_cast<long long>(battery), mid); // Use long long to avoid overflow.
23            }
24          
25            // If total uptime is enough to support n UPSs running for 'mid' duration, search in the higher half.
26            if (sum >= n * mid) {
27                left = mid;
28            } else { // Otherwise, search in the lower half.
29                right = mid - 1;
30            }
31        }
32      
33        // At this point, 'left' is the max runtime possible for n UPSs.
34        return left;
35    }
36};
37
1function maxRunTime(numBatteries: number, batteries: number[]): number {
2    // Define the range for possible maximum run times using BigInt for large numbers handling
3    let low = 0n;
4    let high = 0n;
5
6    // Calculate the sum of all batteries' capacities
7    for (const capacity of batteries) {
8        high += BigInt(capacity);
9    }
10
11    // Use binary search to find the maximum running time
12    while (low < high) {
13        // Calculate the middle value of the current range
14        const mid = (low + high + 1n) >> 1n;
15        let sum = 0n;
16
17        // Sum the minimum between each battery capacity and the mid value
18        for (const capacity of batteries) {
19            sum += BigInt(Math.min(capacity, Number(mid)));
20        }
21
22        // Check if the current mid value can be achieved with the available batteries
23        if (sum >= mid * BigInt(numBatteries)) {
24            // If yes, then mid is a possible maximum run time, so we discard the left half of the search range
25            low = mid;
26        } else {
27            // Otherwise, discard the right half of the search range
28            high = mid - 1n;
29        }
30    }
31
32    // At the end of the while loop, low will have the maximum runtime value, convert it to number before returning
33    return Number(low);
34}
35
Not Sure What to Study? Take the 2-min Quiz๏ผš

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Time and Space Complexity

Time Complexity

The time complexity of the given code is determined by the binary search and the summation of the batteries within the while loop:

  • Binary Search: The binary search runs on the interval from l to r and the interval is halved in each iteration of the loop. Since r is initialized as the sum of all elements in batteries, the maximum number of iterations of the binary search would be O(log(S)) where S is the sum of the batteries array.

  • Summation within Loop: Within each iteration of the binary search, there is a summation of the minima of the individual battery and mid, which is O(N), where N is the number of elements in batteries.

Combining these two steps, the overall time complexity is O(N * log(S)).

Space Complexity

The space complexity of the code is O(1):

  • There are a few variables initialized (l, r, mid) that use constant space.
  • The summation operation uses min() within a generator expression which computes the sum in-place and doesn't require extra space proportional to N.
  • The binary search does not rely on any additional data structures.

Therefore, the additional space used by the program is constant, irrespective of the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ