Watch 10 video solutions for Minimum Time to Repair Cars, a medium level problem involving Array, Binary Search. This walkthrough by NeetCodeIO has 12,787 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Example 1:
Input: ranks = [4,2,3,1], cars = 10 Output: 16 Explanation: - The first mechanic will repair two cars. The time required is 4 * 2 * 2 = 16 minutes. - The second mechanic will repair two cars. The time required is 2 * 2 * 2 = 8 minutes. - The third mechanic will repair two cars. The time required is 3 * 2 * 2 = 12 minutes. - The fourth mechanic will repair four cars. The time required is 1 * 4 * 4 = 16 minutes. It can be proved that the cars cannot be repaired in less than 16 minutes.
Example 2:
Input: ranks = [5,1,8], cars = 6 Output: 16 Explanation: - The first mechanic will repair one car. The time required is 5 * 1 * 1 = 5 minutes. - The second mechanic will repair four cars. The time required is 1 * 4 * 4 = 16 minutes. - The third mechanic will repair one car. The time required is 8 * 1 * 1 = 8 minutes. It can be proved that the cars cannot be repaired in less than 16 minutes.
Constraints:
1 <= ranks.length <= 1051 <= ranks[i] <= 1001 <= cars <= 106Problem Overview: You are given an array ranks where each mechanic with rank r takes r * n² minutes to repair n cars. The goal is to determine the minimum time required for all mechanics combined to repair a given number of cars.
Approach 1: Binary Search on Minimum Time (Time: O(n log T), Space: O(1))
The key observation: if a mechanic has rank r, the maximum cars they can repair in time t is floor(sqrt(t / r)). Instead of simulating repairs directly, search for the smallest time t where the total cars repaired by all mechanics is at least the required number. Use binary search over the time range from 1 to min(rank) * cars². For each candidate time, iterate through the array of ranks and sum how many cars each mechanic can repair. If the total meets the requirement, move left to minimize time; otherwise move right.
This works because the number of cars repaired increases monotonically with time, which makes the problem ideal for binary search on the answer. The check operation runs in linear time across mechanics.
Approach 2: Greedy with Priority Queue (Time: O(cars log n), Space: O(n))
Another way is to simulate the next available repair completion using a min-heap. Each mechanic initially schedules their first car repair taking r * 1² time. Push these into a priority queue ordered by completion time. Repeatedly pop the earliest finishing repair, assign the next car to that mechanic, compute the new completion time r * (k+1)², and push it back. Continue until all cars are assigned.
This greedy simulation always processes the earliest finishing repair next. While intuitive, it becomes slower when the number of cars is large because every repair assignment involves heap operations.
Recommended for interviews: Binary search on time is the expected solution. Interviewers want to see that you recognize the monotonic property and convert the problem into a search over the answer space. The priority queue approach demonstrates understanding of scheduling but does not scale as well for large inputs.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Binary Search on Minimum Time | O(n log T) | O(1) | Best general solution when the answer space is monotonic and constraints are large |
| Greedy with Priority Queue | O(cars log n) | O(n) | Useful for simulation problems or when the number of tasks is relatively small |