2141. Maximum Running Time of N Computers
Approach
Binary search on run time; validate by checking total battery sum >= n * mid.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Binary search reduces search space by half each step, giving O(log n) time. Beyond sorted arrays, apply it on the answer space ("binary search on result") when you can define a monotonic predicate — e.g., "can we achieve X with k resources?"
Greedy algorithms make locally optimal choices at each step, hoping to reach a global optimum. Greedy works when a problem has the "greedy choice property" and "optimal substructure". Common applications: interval scheduling, activity selection, Huffman coding, and jump game.
// Approach: Binary search on run time; validate by checking total battery sum >= n * mid.
// Time: O(b log(sum/n)) Space: O(1)
public class Solution
{
public long MaxRunTime(int n, int[] batteries)
{
long left = 0;
long right = 0;
foreach (int battery in batteries)
right += battery;
while (left < right)
{
long mid = (left + right + 1) >> 1;
long totalUsableCapacity = 0;
foreach (int battery in batteries)
totalUsableCapacity += Math.Min(mid, battery);
if (totalUsableCapacity >= n * mid)
left = mid;
else
right = mid - 1;
}
return left;
}
}