Skip to content

2594. Minimum Time to Repair Cars 👍

  • Time: $O(\log (\min(\texttt{ranks}) \cdot \texttt{cars}^2))$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
 public:
  long long repairCars(vector<int>& ranks, int cars) {
    long l = 0;
    long r = static_cast<long>(ranges::min(ranks)) * cars * cars;

    while (l < r) {
      const long m = (l + r) / 2;
      if (numCarsFixed(ranks, m) >= cars)
        r = m;
      else
        l = m + 1;
    }

    return l;
  }

 private:
  long numCarsFixed(const vector<int>& ranks, long minutes) {
    long carsFixed = 0;
    //    r * n^2 = minutes
    // -> n = sqrt(minutes / r)
    for (const int rank : ranks)
      carsFixed += sqrt(minutes / rank);
    return carsFixed;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
  public long repairCars(int[] ranks, int cars) {
    long l = 0;
    long r = (long) Arrays.stream(ranks).min().getAsInt() * cars * cars;

    while (l < r) {
      final long m = (l + r) / 2;
      if (numCarsFixed(ranks, m) >= cars)
        r = m;
      else
        l = m + 1;
    }

    return l;
  }

  private long numCarsFixed(int[] ranks, long minutes) {
    long carsFixed = 0;
    //    r * n^2 = minutes
    // -> n = sqrt(minutes / r)
    for (final int rank : ranks)
      carsFixed += Math.sqrt(minutes / rank);
    return carsFixed;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
  def repairCars(self, ranks: List[int], cars: int) -> int:
    def numCarsFixed(minutes: int) -> int:
      #    r * n^2 = minutes
      # -> n = sqrt(minutes / r)
      return sum(math.isqrt(minutes // rank) for rank in ranks)

    return bisect.bisect_left(
        range(0, min(ranks) * cars**2), cars,
        key=lambda m: numCarsFixed(m))