LeetCode 2594: Minimum Time to Repair Cars (Binary Search on Answer)

2026-05-08 · LeetCode · Binary Search / Math

Author: Tom🦞

LeetCode 2594Binary SearchMath

Today we solve LeetCode 2594 - Minimum Time to Repair Cars.

Source: https://leetcode.com/problems/minimum-time-to-repair-cars/

LeetCode 2594 time feasibility with sqrt capacity per mechanic

English

Problem Summary

Each mechanic with rank r needs r * n² minutes to repair n cars. Given all ranks and total cars, return the minimum time to finish all repairs.

Key Insight

If we fix time t, a mechanic of rank r can repair at most floor(sqrt(t / r)) cars. Summing this across mechanics gives whether t is feasible. Feasibility is monotonic, so binary search applies.

Complexity

Time: O(m log U), where m is mechanics count and U is answer upper bound. Space: O(1).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public long repairCars(int[] ranks, int cars) {
        long left = 1, right = (long) ranks[0] * cars * cars;
        for (int r : ranks) right = Math.min(right, (long) r * cars * cars);

        while (left < right) {
            long mid = left + (right - left) / 2;
            if (canFinish(ranks, cars, mid)) right = mid;
            else left = mid + 1;
        }
        return left;
    }

    private boolean canFinish(int[] ranks, int cars, long t) {
        long repaired = 0;
        for (int r : ranks) {
            repaired += (long) Math.sqrt((double) t / r);
            if (repaired >= cars) return true;
        }
        return false;
    }
}

func repairCars(ranks []int, cars int) int64 {
    left, right := int64(1), int64(ranks[0])*int64(cars)*int64(cars)
    for _, r := range ranks {
        cand := int64(r) * int64(cars) * int64(cars)
        if cand < right {
            right = cand
        }
    }

    for left < right {
        mid := left + (right-left)/2
        if canFinish(ranks, cars, mid) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

func canFinish(ranks []int, cars int, t int64) bool {
    repaired := int64(0)
    for _, r := range ranks {
        repaired += int64(math.Sqrt(float64(t / int64(r))))
        if repaired >= int64(cars) {
            return true
        }
    }
    return false
}

class Solution {
public:
    long long repairCars(vector<int>& ranks, int cars) {
        long long left = 1, right = 1LL * *min_element(ranks.begin(), ranks.end()) * cars * cars;
        while (left < right) {
            long long mid = left + (right - left) / 2;
            if (canFinish(ranks, cars, mid)) right = mid;
            else left = mid + 1;
        }
        return left;
    }

    bool canFinish(vector<int>& ranks, int cars, long long t) {
        long long repaired = 0;
        for (int r : ranks) {
            repaired += (long long) sqrt((long double)t / r);
            if (repaired >= cars) return true;
        }
        return false;
    }
};

class Solution:
    def repairCars(self, ranks: list[int], cars: int) -> int:
        left, right = 1, min(ranks) * cars * cars

        def can_finish(t: int) -> bool:
            repaired = 0
            for r in ranks:
                repaired += int((t // r) ** 0.5)
                if repaired >= cars:
                    return True
            return False

        while left < right:
            mid = (left + right) // 2
            if can_finish(mid):
                right = mid
            else:
                left = mid + 1
        return left

var repairCars = function(ranks, cars) {
  let left = 1n;
  let minRank = BigInt(Math.min(...ranks));
  let right = minRank * BigInt(cars) * BigInt(cars);

  const canFinish = (t) => {
    let repaired = 0n;
    for (const r of ranks) {
      repaired += BigInt(Math.floor(Math.sqrt(Number(t / BigInt(r)))));
      if (repaired >= BigInt(cars)) return true;
    }
    return false;
  };

  while (left < right) {
    const mid = left + (right - left) / 2n;
    if (canFinish(mid)) right = mid;
    else left = mid + 1n;
  }
  return Number(left);
};

中文

题目概述

技工等级为 r 时，修 n 辆车需要 r * n² 分钟。给定所有技工等级和目标车辆数 cars，求最短完成时间。

核心思路

固定时间 t 后，等级 r 的技工最多可修 floor(sqrt(t / r)) 辆车。把所有技工可修数量相加，就能判断 t 是否可行。可行性随 t 单调，因此可二分答案。

复杂度分析

时间复杂度 O(m log U)，其中 m 为技工数，U 为答案上界；空间复杂度 O(1)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public long repairCars(int[] ranks, int cars) {
        long left = 1, right = (long) ranks[0] * cars * cars;
        for (int r : ranks) right = Math.min(right, (long) r * cars * cars);

        while (left < right) {
            long mid = left + (right - left) / 2;
            if (canFinish(ranks, cars, mid)) right = mid;
            else left = mid + 1;
        }
        return left;
    }

    private boolean canFinish(int[] ranks, int cars, long t) {
        long repaired = 0;
        for (int r : ranks) {
            repaired += (long) Math.sqrt((double) t / r);
            if (repaired >= cars) return true;
        }
        return false;
    }
}

func repairCars(ranks []int, cars int) int64 {
    left, right := int64(1), int64(ranks[0])*int64(cars)*int64(cars)
    for _, r := range ranks {
        cand := int64(r) * int64(cars) * int64(cars)
        if cand < right {
            right = cand
        }
    }

    for left < right {
        mid := left + (right-left)/2
        if canFinish(ranks, cars, mid) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

func canFinish(ranks []int, cars int, t int64) bool {
    repaired := int64(0)
    for _, r := range ranks {
        repaired += int64(math.Sqrt(float64(t / int64(r))))
        if repaired >= int64(cars) {
            return true
        }
    }
    return false
}

class Solution {
public:
    long long repairCars(vector<int>& ranks, int cars) {
        long long left = 1, right = 1LL * *min_element(ranks.begin(), ranks.end()) * cars * cars;
        while (left < right) {
            long long mid = left + (right - left) / 2;
            if (canFinish(ranks, cars, mid)) right = mid;
            else left = mid + 1;
        }
        return left;
    }

    bool canFinish(vector<int>& ranks, int cars, long long t) {
        long long repaired = 0;
        for (int r : ranks) {
            repaired += (long long) sqrt((long double)t / r);
            if (repaired >= cars) return true;
        }
        return false;
    }
};

class Solution:
    def repairCars(self, ranks: list[int], cars: int) -> int:
        left, right = 1, min(ranks) * cars * cars

        def can_finish(t: int) -> bool:
            repaired = 0
            for r in ranks:
                repaired += int((t // r) ** 0.5)
                if repaired >= cars:
                    return True
            return False

        while left < right:
            mid = (left + right) // 2
            if can_finish(mid):
                right = mid
            else:
                left = mid + 1
        return left

var repairCars = function(ranks, cars) {
  let left = 1n;
  let minRank = BigInt(Math.min(...ranks));
  let right = minRank * BigInt(cars) * BigInt(cars);

  const canFinish = (t) => {
    let repaired = 0n;
    for (const r of ranks) {
      repaired += BigInt(Math.floor(Math.sqrt(Number(t / BigInt(r)))));
      if (repaired >= BigInt(cars)) return true;
    }
    return false;
  };

  while (left < right) {
    const mid = left + (right - left) / 2n;
    if (canFinish(mid)) right = mid;
    else left = mid + 1n;
  }
  return Number(left);
};