2594. Minimum Time to Repair Cars

Approach

Binary search on time; mechanic with rank r fixes floor(sqrt(t/r)) cars; validate sum >= n.

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

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?"

2594.cs

// Approach: Binary search on time; mechanic with rank r fixes floor(sqrt(t/r)) cars; validate sum >= n.
// Time: O(n log(min * n²)) Space: O(1)

public class Solution
{
    public long RepairCars(int[] ranks, int cars)
    {
        long l = 0;
        long r = (long)ranks.Min() * cars * cars;

        while (l < r)
        {
            long m = (l + r) / 2;
            if (NumCarsFixed(ranks, m) >= cars)
                r = m;
            else
                l = m + 1;
        }

        return l;
    }

    private long NumCarsFixed(int[] ranks, long minutes)
    {
        long carsFixed = 0;
        foreach (var rank in ranks)
            carsFixed += (long)Math.Sqrt(minutes / rank);
        return carsFixed;
    }
}

Was this solution helpful?