We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Running Time of N Computers

Number: 2263

Difficulty: Hard

Paid? No

Companies: Amazon, Adobe, Flipkart, Deutsche Bank

Problem Description

Given n computers and an array of batteries where each battery’s value indicates the number of minutes it can run a computer, determine the maximum number of minutes you can run all n computers simultaneously. You may initially place at most one battery in each computer and can later swap batteries between computers arbitrarily fast. Batteries cannot be recharged.

Key Insights

  • The total available energy is the sum of all battery capacities.
  • The maximum running time T is bounded by the total energy divided by n.
  • For each battery, only up to T minutes of its energy are useful.
  • Use binary search on T and for each candidate, check if the sum of min(battery, T) over all batteries is at least n * T.

Space and Time Complexity

Time Complexity: O(m * log(s)) where m is the number of batteries and s is the sum of battery capacities divided by n. Space Complexity: O(1) additional space (ignoring input storage).

Solution

We use binary search over the possible running times T. The minimum T is 0, and the maximum is the sum of all batteries divided by n. For each candidate T, we check if it is feasible to run n computers by accumulating min(battery, T) from each battery — since a battery can contribute at most T minutes toward the required runtime if it has extra energy. If the total accumulated energy is at least T * n, then running the computers for T minutes is possible. Accordingly, we adjust the binary search bounds until we identify the maximum feasible T. This approach leverages binary search and a greedy aggregate over battery capacities to meet the running time requirement.

Code Solutions

# Function to compute maximum runtime for n computers using batteries array
def maxRunTime(n, batteries):
    # Calculate total available energy from batteries
    total_energy = sum(batteries)
    # Set lower and upper bounds for binary search
    lo, hi = 0, total_energy // n

    # Define a helper function to determine if it is feasible to run for 'time' minutes
    def feasible(time):
        total = 0
        for battery in batteries:
            # Each battery can contribute at most 'time' minutes
            total += min(battery, time)
            # Early exit if sufficient energy is collected
            if total >= time * n:
                return True
        return total >= time * n

    # Binary search loop to find the maximum feasible runtime
    while lo < hi:
        mid = (lo + hi + 1) // 2  # Bias towards the upper half
        if feasible(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo

# Example usage:
if __name__ == "__main__":
    n = 2
    batteries = [3, 3, 3]
    print(maxRunTime(n, batteries))  # Expected output: 4
← Back to All Questions