Minimum Time to Repair Cars - Solution & Explanation
Problem Statement
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 <= 106
Approach Overview
Problem 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 1: Binary Search on Minimum Time
This approach leverages binary search to find the minimum time required to repair all the cars. We observe that if a mechanic with rank r repairs n cars, they can do so in r * n^2 minutes. Our goal is to minimize the maximum amount of time any mechanic would spend to repair the cars. We perform binary search on time to decide the least time possible where all cars can be finished.
The key observation here is that given a time, we can check if it's possible for all cars to be repaired within that time by distributing cars among all mechanics optimally.
In this C solution, we define a helper function canRepair that checks if it's possible to repair all cars within a given time. This function computes how many cars each mechanic can potentially repair within that time. The main function uses binary search over time to find the minimum time required to repair all cars.
Complexity
Time Complexity: O(n * log(cars * max_rank * cars)), where max_rank is the highest rank value.
Space Complexity: O(1).
Approach 2: Greedy with Priority Queue
This approach uses a greedy algorithm with a priority queue (or a min-heap) to assign cars to mechanics such that the total time taken is minimized. The priority queue is used to always pick the mechanic who will complete their next car repair in the shortest time. This approach minimizes the overall time in a different manner compared to the binary search method.
This C++ solution uses a priority queue to simulate a process where each mechanic receives cars to repair in a greedy manner. It keeps track of each mechanic's total time and cars repaired, and always picks the mechanic with the current least time to assign the next car.
Complexity
Time Complexity: O(cars * log(n)).
Space Complexity: O(n).
Approach 3: Binary Search
We notice that the longer the repair time, the more cars are repaired. Therefore, we can use the repair time as the target of binary search, and binary search for the minimum repair time.
We define the left and right boundaries of the binary search as left=0, right=ranks[0] times cars times cars. Next, we binary search for the repair time mid, and the number of cars each mechanic can repair is \lfloor \sqrt{\frac{mid}{r}} \rfloor, where \lfloor x \rfloor represents rounding down. If the number of cars repaired is greater than or equal to cars, it means that the repair time mid is feasible, we reduce the right boundary to mid, otherwise we increase the left boundary to mid+1.
Finally, we return the left boundary.
The time complexity is O(n times log M), and the space complexity is O(1). Here, n is the number of mechanics, and M is the upper bound of the binary search.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Binary Search on Minimum Time | Time Complexity: |
| Greedy with Priority Queue | Time Complexity: |
| Binary Search | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Minimum Time to Repair Cars - Leetcode 2594 - Python • NeetCodeIO • 13,082 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimum Time to Repair Cars easy or hard?
Minimum Time to Repair Cars Python/Java solution
How to solve Minimum Time to Repair Cars in O(n)?
What is the best approach for Minimum Time to Repair Cars?
Is Minimum Time to Repair Cars asked at Google/Amazon/Meta?
What data structure is used in Minimum Time to Repair Cars?
What is the time complexity of Minimum Time to Repair Cars?
Ready to solve this problem?
Practice Minimum Time to Repair Cars with our built-in code editor and test cases.
Practice on FleetCode