#2141

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Maximum Running Time of N Computers

Solve the problem of determining the maximum running time of n computers using a set of batteries.

Problem Statement

You are given n computers and an array of batteries where each battery can power a computer for a certain amount of time. Your task is to determine the maximum number of minutes you can run all n computers simultaneously using the available batteries. Initially, each computer can have one battery inserted. After that, batteries can be swapped at any time, but no battery can be recharged.

For each given running time, the goal is to check if it is possible to run all computers simultaneously. This is done by testing if a specific running time can be achieved by optimally distributing the batteries between the computers. The answer involves finding the maximum possible running time.

Examples

Example 1

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

Output: 4

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

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 <= 105
1 <= batteries[i] <= 109

Solution Approach

Binary Search on Time

Use binary search over the possible running times, with the range starting from 0 to the total sum of battery times. For each midpoint, check if it is feasible to run all computers for that amount of time.

Feasibility Check

For each binary search midpoint (representing a possible running time), check if the total time that can be provided by all batteries is sufficient for n computers. This requires summing up the maximum time each battery can provide and comparing it to the required total.

Greedy Battery Distribution

After determining a valid running time, use a greedy approach to maximize the usage of each battery. Insert batteries into computers and swap them as necessary to achieve the desired running time.

Complexity Analysis

Metric	Value
Time	O(m \cdot\log k)
Space	O(1)

The time complexity is O(m \cdot\log k), where m is the number of batteries, and k is the total time range. The space complexity is O(1), as the solution only requires a few extra variables for tracking and calculation.

What Interviewers Usually Probe

Check if the candidate understands binary search applied to a valid answer space.
Look for the candidate’s approach to checking the feasibility of each running time in the binary search range.
Assess how the candidate balances the greedy algorithm with the binary search approach.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the battery distribution logic: ensuring all batteries are used efficiently is key.
Overcomplicating the binary search bounds: the search range is simply between 0 and the total sum of battery times.
Failing to correctly swap batteries between computers at optimal moments, leading to inefficient running times.

Follow-up variants

Varying the number of computers n, keeping battery count the same.
Varying the distribution of battery times: very large vs small battery times.
Introducing constraints where batteries can only be swapped a limited number of times.

FAQ

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

The time complexity is O(m \cdot\log k), where m is the number of batteries, and k is the total time range.

How does binary search help in solving the Maximum Running Time of N Computers?

Binary search is used to find the maximum possible running time by checking if a given running time is feasible using the available batteries.

Can I use a greedy algorithm alone to solve the Maximum Running Time of N Computers?

A greedy algorithm can help in distributing batteries efficiently, but binary search is necessary to find the optimal running time.

What is the key approach in solving the Maximum Running Time of N Computers?

The key approach is binary search over the possible running times combined with a greedy method for battery distribution.

What are the common pitfalls when solving the Maximum Running Time of N Computers?

Common pitfalls include misunderstanding battery distribution, misapplying binary search bounds, and inefficient battery swapping strategies.

terminal

Solution

Solution 1: 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$.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def maxRunTime(self, n: int, batteries: List[int]) -> int:
        l, r = 0, sum(batteries)
        while l < r:
            mid = (l + r + 1) >> 1
            if sum(min(x, mid) for x in batteries) >= n * mid:
                l = mid
            else:
                r = mid - 1
        return l

Continue Practicing

#2071 maximum number of tasks you can assign #2234 maximum total beauty of the gardens #2271 maximum white tiles covered by a carpet