'2025/03/16'에 해당되는 글 1건

Leetcode Problem:

• Minimum Time to Repair Cars

Summary

• Find the minimum time to repair all cars given the ranks of mechanics and the total number of cars.

Approach

• Binary Search: The solution uses binary search to find the minimum time to repair all cars
• It initializes two pointers, l and r, to the minimum and maximum possible times
• It then calculates the midpoint and checks if the number of cars that can be repaired within the time limit is less than or equal to the total number of cars
• If it is, it updates the minimum time and moves the left pointer to the right
• Otherwise, it updates the maximum time and moves the right pointer to the left
• This process continues until the two pointers meet, and the minimum time is returned.

Complexity

• O(n log m) where n is the number of mechanics and m is the maximum rank

Explanation

• The solution first initializes two pointers, l and r, to the minimum and maximum possible times
• It then calculates the midpoint and checks if the number of cars that can be repaired within the time limit is less than or equal to the total number of cars
• If it is, it updates the minimum time and moves the left pointer to the right
• Otherwise, it updates the maximum time and moves the right pointer to the left
• This process continues until the two pointers meet, and the minimum time is returned
• The time complexity is O(n log m) because the solution uses binary search, which has a time complexity of O(log m), and it needs to iterate over the mechanics, which takes O(n) time.

Solution Code:

class Solution {
public:
    long long repairCars(vector& ranks, int cars) {
        long long l = 0;
        long long r = 100000000000000;
        long long ans = 0;
        while(l <= r){
            long long mid = (l + r ) / 2;
            long long repairCar = 0;
            for(int i = 0 ; i < ranks.size(); i++){
                long long tmp = mid/ranks[i];
                repairCar += sqrt(tmp);
            }
            if(repairCar < cars){
                l = mid + 1;
            } else{
                ans = mid;
                r = mid - 1;
            }
        }
        return ans;
    }
};