2594.minimum-time-to-repair-cars.md

2594. Minimum Time to Repair Cars

Hints

• What happens to the number of cars a mechanic can repair as time increases?
• Can you check if a given time is enough to repair all cars?

Binary Search

• Monotonicity: If a given time t is enough to repair all cars, then any larger time is also enough. If t is not enough, any smaller time is also not enough. This property allows us to use binary search on the answer space.
• Lower bound: The minimum possible time is 1. No mechanic can repair a car in less than 1 unit of time. Or the tightest lower bound is min(ranks) * 1, which is the fastest mechanic to repair 1 car.
• Upper bound: We can assign the slowest mechanic to repair all cars, that would be max(ranks) * cars^2. Or the tightest upper bound is min(ranks) * cars^2, which is the fastest mechanic to repair all cars alone.
• Feasibility: For a given time, sum up floor(sqrt(time / rank)) for each mechanic. If the total is at least the required number of cars, the time is feasible.
• How to observe binary search applies: The problem asks for the minimum time to satisfy a monotonic condition (repairing all cars), and the feasibility function is efficiently checkable for any candidate time. This is a classic "binary search on value" pattern.

TODO: Understand the bounds, why the upper bound is min(ranks) * cars^2? And why the lower bound is min(ranks) * 1, can't be min(ranks) * cars^2 or cars? Seem to be similar to 2187. Minimum Time to Complete Trips

• The minimum time repair all the cars 最快能修好所有車？要最快我就找修車最快的師傅去修所有車就好
• In this problem what we're trying to do is to minimise amount of time spent repairing cars. And this minimised answer can't be worse than in situation when we allocate all of the cars to a single mechanic.
• It's because we are looking for the min time to complete repairing all cars, and the fastest mechanic(minRank) could potentially repair all cars alone.
• 二分上界为 min(ranks) * cars^2 ，即让能力值最低（修车最快）的人修好所有车所需要的时间。
• 我们只要找到一个可行方案，这个方案都可以成为上界，然后去找更小的可行方案。所以任何一个机械工的 ranks[i] * cars^2 都可以是上界。然后为了使二分的次数更少，选 min(ranks) * cars^2。

fun repairCars(ranks: IntArray, cars: Int): Long {
    val cars = cars.toLong()
    var left = 1L
    var right = ranks.min() * cars * cars 
    while (left <= right) {
        val middle = left + (right - left) / 2
        val feasible = canRepareAllCars(ranks, cars, middle)
        if (feasible) {
            right = middle - 1
        } else {
            left = middle + 1
        }
    }
    return left
}

// Given a time, how many total cars can be repaired? >= cars?
private fun canRepareAllCars(ranks: IntArray, cars: Long, time: Long): Boolean {
    var repaired = 0L
    for (rank in ranks) {
        repaired += sqrt(time.toDouble() / rank).toLong()
    }
    return cars <= repaired
}

• Time Complexity: O(n * log(maxTime)), where n is the number of mechanics, and maxTime is the search space.
• Space Complexity: O(1).

Edge Cases

• Only one mechanic: all cars must be repaired by one person, so time is rank * cars^2.
• All mechanics have the same rank: cars are distributed as evenly as possible.
• Large values for cars or ranks: ensure no overflow (use Long).
• If cars is 1, answer is min(ranks).

WA

I set the wrong lower bound, I think all cars can be repaired in 1 time unit, but it is not true.

fun repairCars(ranks: IntArray, cars: Int): Long {
    val cars = cars.toLong()

    // Wrong bound
    var left = cars // I think all cars can be repaired in 1 time unit
    var right = ranks.max() * cars * cars // Showest mechanics to repair all cars
    while (left <= right) {
        val middle = left + (right - left) / 2
        val feasible = canRepareAllCars(ranks, cars, middle)
        if (feasible) {
            right = middle - 1
        } else {
            left = middle + 1
        }
    }
    return left
}

private fun canRepareAllCars(ranks: IntArray, cars: Long, time: Long): Boolean {
    // Given a time, how many total cars can be repaired? >= cars?
    var repaired = 0L
    for (rank in ranks) {
        repaired += sqrt(time.toDouble() / rank).toLong()
    }
    return cars <= repaired
}

/**

Longer time, more repaired cars: monotonic

ranks = 4, 2, 3, 1
t = 1   W, X, Y, Z < cars
...
t = 16  W, X, Y, Z >= cars
t = 17  >= cars

lower bound: showest mechanics to repair all cars
upper bound: fastest mechanics to repair all cars

Given a time, how many cars can be repaired?
formular transit:
time     cars
r * n^2     n
  T  = sqrt(T / r)
 */