Minimum time to repair cars

Array Binary Search

59.6% acceptance

Feb 25, 2026

1338

You are given an integer array ranks representing the ranks of some mechanics. ranksi is the rank of the ith mechanic. A mechanic with a rank r can repair n cars in r * n2 minutes. You are also given an integer cars representing the total number of cars waiting in the garage to be repaired. Return the minimum time taken to repair all the cars. Note: All the mechanics can repair the cars simultaneously.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn repair_cars(ranks: Vec<i32>, cars: i32) -> i64 {
    // Binary search on time t.
    // For time t, mechanic with rank r can repair floor(sqrt(t/r)) cars.
    // Total cars repaired at time t = sum over all mechanics of floor(sqrt(t/r)).
    // Find minimum t such that total >= cars.
    let cars = cars as i64;
    let min_rank = *ranks.iter().min().unwrap() as i64;
    let mut lo = 1i64;
    let mut hi = min_rank * cars * cars;
    while lo < hi {
      let mid = lo + (hi - lo) / 2;
      let total: i64 = ranks.iter().map(|&r| ((mid / r as i64) as f64).sqrt() as i64).sum();
      if total >= cars {
        hi = mid;
      } else {
        lo = mid + 1;
      }
    }
    lo
  }
}