⚡Flashcard Drill➔
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

  1. Binary search on the time t: "can all cars be repaired within t minutes" is monotone in t.
  2. A mechanic with rank r can repair floor(sqrt(t / r)) cars within t minutes, since r * n^2 <= t.
  3. Sum over all mechanics and compare with cars.
  4. 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 <= t for n with floats: math.sqrt(t / r) loses precision for large values; isqrt(t // r) is exact because isqrt(floor(t/r)) == floor(sqrt(t/r)) for integers.
  • Setting the upper bound too low: one mechanic alone needs max(ranks) * cars^2 minutes, 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.
🎯 Drill This Card Now➔

🧩 Related Binary Search Problems