Maximum Running Time of N Computers

Maximum Running Time of N Computers

1. What is this problem about?

The Maximum Running Time of N Computers interview question is a high-level scheduling and load-balancing problem. You have n computers and a set of batteries with various capacities. You want to run all n computers simultaneously for as long as possible using these batteries. You can swap batteries between computers at any time, and the swap is instantaneous.

The goal is to find the maximum time T such that all n computers can run for T minutes.

2. Why is this asked in interviews?

This Maximum Running Time of N Computers coding problem is a "Hard" difficulty question asked by Flipkart and Google. It tests your ability to recognize a "Binary Search on Answer" pattern. It's not immediately obvious that you can check if a time T is possible. It evaluates your ability to handle large constraints and find a non-obvious greedy condition that determines feasibility.

3. Algorithmic pattern used

The Array, Sorting, Binary Search, Greedy interview pattern is applied here.

1. The possible running time ranges from 0 to sum(batteries) / n.
2. Binary search for the maximum time T.
3. For a given T, check if it's feasible:
   • Each battery can contribute at most T minutes to the total pool (since it can only be in one computer at a time).
   • Total energy available for a target time T is sum(min(battery_capacity, T) for battery in batteries).
   • If total_energy >= n * T, then time T is feasible.

4. Example explanation

n = 2 computers, batteries = [3, 3, 3].

• Try T = 4:
  • Energy from bat 1: min(3, 4) = 3.
  • Energy from bat 2: min(3, 4) = 3.
  • Energy from bat 3: min(3, 4) = 3.
  • Total energy = 9. Need 2 * 4 = 8.
  • 9 >= 8, so T=4 is possible.
• Try T = 5:
  • Total energy = 3 + 3 + 3 = 9. Need 2 * 5 = 10.
  • 9 < 10, so T=5 is impossible. Through binary search, we'd find the max T is 4.5 (if continuous) or 4 (if discrete).

5. Common mistakes candidates make

The biggest mistake in the Maximum Running Time of N Computers coding problem is trying to use a greedy approach like "always use the largest batteries first" without the binary search framework. This fails because of the swapping rule. Another mistake is not capping the battery contribution at T in the feasibility check. Candidates also often struggle with the data types, as the total sum of battery capacities can exceed the range of a 32-bit integer.

6. Interview preparation tip

Whenever you are asked to "maximize the minimum" or "find the maximum possible value" and there's a clear range, always consider Binary Search on the result. The key is to simplify the problem into a "Can I do this for value X?" question, which is often much easier to answer than finding the optimal value directly.