Minimum Time to Repair Cars

Minimum Time to Repair Cars

What is this problem about?

The Minimum Time to Repair Cars problem gives you a list of mechanics, each with a "rank" determining how fast they work. A mechanic with rank r takes r * n² minutes to repair n cars. All mechanics work simultaneously. Find the minimum total time to repair all cars collectively. This Minimum Time to Repair Cars coding problem is a clean binary search on the answer application.

Why is this asked in interviews?

Deloitte, Microsoft, Meta, Amazon, and Google ask this because it's a well-scoped binary search on the answer problem with a simple feasibility check. It validates that candidates understand how parallel workers with different rates combine, and that the optimal time is found by searching over possible values rather than deriving a formula. The array and binary search interview pattern is directly applied.

Algorithmic pattern used

Binary search on total time T. For a given time T, mechanic with rank r can repair floor(sqrt(T/r)) cars. Sum the max-car counts across all mechanics. If the total ≥ required cars, T is feasible. Binary search on T in range [1, min_rank * total_cars²]. Return the minimum feasible T.

Example explanation

Mechanics: [4, 2, 3], total cars = 10.

• T = 16: rank 4 → sqrt(16/4)=2 cars; rank 2 → sqrt(16/2)=2.8→2 cars; rank 3 → sqrt(16/3)=2.3→2 cars. Total = 6 < 10. Not feasible.
• T = 50: rank 4 → sqrt(50/4)=3.5→3; rank 2 → sqrt(50/2)=5; rank 3 → sqrt(50/3)=4. Total = 12 ≥ 10. Feasible.
• Binary search finds minimum T = 16 with adjusted numbers... or the correct minimum after full binary search.

Common mistakes candidates make

• Computing T / r then taking sqrt without floor (floating point drift).
• Binary search upper bound too small — should be min_rank * cars².
• Not using integer square root to avoid floating point errors.
• Forgetting that parallel workers reduce total time significantly.

Interview preparation tip

Repair/build/produce problems with parallel workers always follow the binary search on answer pattern. The feasibility check: given time T, how many units can all workers collectively produce? Sum floor(sqrt(T/rank)) for each worker (or the relevant formula). Set your binary search upper bound conservatively large (usually slowest_single_worker * total_units). Practice integer square root computation cleanly: int_sqrt = int(T/r ** 0.5) and verify with isqrt functions where available.