NeetCode #283LC-2594MediumBinary Search
← Back to All Problems#283 · #2594 · Minimum Time to Repair Cars(修车的最少时间)
📌 Problem Statement & Constraints
You are given an integer array
ranks where ranks[i] is the rank of the i-th mechanic, and an integer cars. A mechanic with rank r takes r * n^2 minutes to repair n cars. All mechanics work simultaneously. Return the minimum time to repair all cars. Constraints: 1 <= ranks.length <= 10^5, 1 <= ranks[i] <= 100, 1 <= cars <= 10^6.💡 Core Algorithmic Approaches
- Binary search on the time
t: "can all cars be repaired withintminutes" is monotone int. - A mechanic with rank
rcan repairfloor(sqrt(t / r))cars withintminutes, sincer * n^2 <= t. - Sum over all mechanics and compare with
cars. - The upper bound is
max(ranks) * cars^2, which one mechanic alone would need.
💻 Benchmark Python3 Implementation
class Solution:
def repairCars(self, ranks: List[int], cars: int) -> int:
from math import isqrt
lo, hi = 1, max(ranks) * cars * cars
while lo < hi:
mid = (lo + hi) // 2
# cars each mechanic can finish within mid minutes
total = sum(isqrt(mid // r) for r in ranks)
if total >= cars:
hi = mid # feasible -> try less time
else:
lo = mid + 1
return lo⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log(max(ranks) * cars^2)): each check is O(n).
💾 Space Complexity
O(1): a few scalars.
⚠️ Interview Pitfalls & Follow-ups
- Solving
r * n^2 <= tfornwith floats:math.sqrt(t / r)loses precision for large values;isqrt(t // r)is exact becauseisqrt(floor(t/r)) == floor(sqrt(t/r))for integers. - Setting the upper bound too low: one mechanic alone needs
max(ranks) * cars^2minutes, which is the safe upper bound. - Using
total == cars: more capacity than needed is fine, so the condition is>=. - Forgetting that mechanics work in parallel: the total is a sum of individual capacities, not a max.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.