← Back to Index

📚 Maximum Running Time of N Computers – Java Cheat Sheet

📌 What Is It?

The Maximum Running Time of N Computers problem involves determining the maximum number of hours N computers can run simultaneously using a given number of batteries. Each battery has a specific capacity, and the goal is to distribute the batteries optimally to maximize the runtime.

🧱 Pattern Template

class Solution {
    public long maxRunTime(int n, int[] batteries) {
        long totalPower = 0;
        for (int battery : batteries) {
            totalPower += battery;
        }

        long left = 1, right = totalPower / n;

        while (left < right) {
            long mid = right - (right - left) / 2;

            if (canRun(n, batteries, mid)) {
                left = mid; // Try a larger runtime
            } else {
                right = mid - 1; // Try a smaller runtime
            }
        }

        return left;
    }

    private boolean canRun(int n, int[] batteries, long runtime) {
        long availablePower = 0;

        for (int battery : batteries) {
            availablePower += Math.min(battery, runtime);

            if (availablePower >= runtime * n) {
                return true;
            }
        }

        return false;
    }
}

📊 Time Complexity

• Binary Search: O(log(T)), where T is the total power divided by N.
• Validation: O(M), where M is the number of batteries.
• Overall Complexity: O(M log(T)).

✅ Use Cases

• Optimizing resource allocation for maximum runtime
• Applications in power management and scheduling

📘 Common LeetCode Problems

• 2141. Maximum Running Time of N Computers [Hard] Binary Search

🧪 Example: Maximum Running Time of N Computers

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

Explanation:
- Distribute the batteries as [3, 1] and [3, 1].
- The maximum runtime is 4 hours.

▶️ View Animation

💡 Pro Tips

• Use binary search to efficiently find the maximum runtime.
• Edge cases: fewer batteries than computers, batteries with zero capacity.
• Precompute the total power to set the binary search bounds.