Minimum Time to Repair Cars

medium binary search search the answer array

Problem

Each mechanic i has a rank ranks[i]. A mechanic of rank r can repair n cars in r · n² minutes. Given cars total cars and that all mechanics work simultaneously, return the minimum minutes needed to repair every car.

The trick: in a fixed budget of t minutes, a rank-r mechanic can finish n = ⌊√(t / r)⌋ cars. The total cars repairable in t minutes only grows as t grows, so we can binary-search the smallest feasible t.

Inputranks = [4,2,3,1], cars = 10

Output16

In 16 min: ranks 4,2,3 each do 2 cars (4·4, 2·4, 3·4 ≤ 16) and rank 1 does 4 cars (1·16 = 16). Total 2+2+2+4 = 10 ✓. No smaller time works.

ranks (comma-separated)

cars

def repairCars(ranks, cars):
    # cars finished by all mechanics within t minutes
    def feasible(t):
        total = 0
        for r in ranks:
            total += isqrt(t // r)   # n = floor(sqrt(t / r))
            if total >= cars:
                return True
        return total >= cars
    # answer is bounded by the fastest single mechanic (smallest rank) doing all cars
    lo, hi = 1, min(ranks) * cars * cars
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid             # mid works, try smaller
        else:
            lo = mid + 1         # too slow, need more time
    return lo

function repairCars(ranks, cars) {
  // cars finished by all mechanics within t minutes
  const feasible = (t) => {
    let total = 0;
    for (const r of ranks) {
      total += Math.floor(Math.sqrt(t / r)); // n = floor(sqrt(t/r))
      if (total >= cars) return true;
    }
    return total >= cars;
  };
  // answer is bounded by the fastest single mechanic (smallest rank) doing all cars
  let lo = 1, hi = Math.min(...ranks) * cars * cars;
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (feasible(mid)) hi = mid;     // mid works, try smaller
    else lo = mid + 1;               // too slow, need more time
  }
  return lo;
}

long repairCars(int[] ranks, int cars) {
    int minRank = Integer.MAX_VALUE;
    for (int r : ranks) minRank = Math.min(minRank, r);
    long lo = 1, hi = (long) minRank * cars * cars;
    while (lo < hi) {
        long mid = lo + (hi - lo) / 2;
        if (feasible(ranks, cars, mid)) hi = mid; // works, shrink
        else lo = mid + 1;                        // too slow
    }
    return lo;
}
boolean feasible(int[] ranks, int cars, long t) {
    long total = 0;
    for (int r : ranks) {
        total += (long) Math.sqrt((double) t / r); // floor sqrt(t/r)
        if (total >= cars) return true;
    }
    return total >= cars;
}

long long repairCars(vector<int>& ranks, int cars) {
    int minRank = *min_element(ranks.begin(), ranks.end());
    long long lo = 1, hi = (long long) minRank * cars * cars;
    auto feasible = [&](long long t) {
        long long total = 0;
        for (int r : ranks) {
            total += (long long) sqrtl((long double) t / r); // floor sqrt
            if (total >= cars) return true;
        }
        return total >= cars;
    };
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (feasible(mid)) hi = mid;   // works, shrink
        else lo = mid + 1;             // too slow
    }
    return lo;
}

Explanation

This is a classic binary search on the answer. Instead of searching an array, we search the space of possible times and use a yes/no feasibility test.

The monotonic predicate. Define feasible(t) = "can all the cars be repaired within t minutes?". A mechanic of rank r repairing n cars takes r·n² minutes, so within a budget of t minutes that mechanic can finish n = ⌊√(t / r)⌋ cars. Summing over every mechanic gives the total cars repairable in t minutes. As t increases, every term can only stay the same or grow, so the predicate is monotone: once it becomes true it stays true. That monotonicity is exactly what makes binary search valid.

Bounds. The smallest sensible time is 1. For an upper bound, imagine the FASTEST mechanic (smallest rank = min(ranks)) doing all the cars alone, which takes min(ranks) · cars² minutes — a valid upper bound since one mechanic can always finish everything within that time, and the team is at least as fast, guaranteeing feasibility at hi.

The search. We keep a window [lo, hi] known to contain the answer. Each round we test mid. If feasible(mid) we move hi = mid (this time works, but maybe a smaller one does too). Otherwise lo = mid + 1 (mid is too tight). The loop ends when lo == hi, the smallest feasible time.

For ranks = [4,2,3,1], cars = 10 the window collapses to 16: at 16 minutes the mechanics complete 2+2+2+4 = 10 cars, and at 15 minutes they fall short.

Time: O(n · log(min(ranks) · cars²)) Space: O(1)