DEV Community

Prashant Mishra
Prashant Mishra

Posted on

Minimum Time to repair cars

Problem
TC: O(nlog(k)), where k is the max time in the range between 1 to r*n^2

class Solution {
    public long repairCars(int[] ranks, int cars) {
        long low = 1;// atleat one lowute will be needed 
        long high = 0;
        for(int i : ranks){
            high = Math.max(i,high);//mechanic with the largest rank will take greatest time to process all the cars
        }
        high = high *cars * cars;
        long val = 0;
        while(low<=high){
            long mid = (long)(low+high)/2l;

            if(check(mid,ranks,cars)){
                val = mid;
                high = mid-1;
            }
            else low = mid+1;
        }
        return val;
    }

    public boolean check(long time, int ranks[], int cars){
        //now we have to find out how much cars a mechanic can fix in given time 'time'
        //we know r*n^2 = time i.e rankOfMechanic*Math.pow(noOfCars,2) will give the time each mechanic will take to process n cars
        //we have to find out no. of cars for each mechanic for the give time
        //if total car processed in time 'time' is greater than or equal to 'cars' then the time is good enough time 
        //and we can look for time smaller that the time 'time'
        //n = Math.sqrt((time/r))

        int totalCar= 0;
        for(int rank : ranks){
            totalCar+= Math.sqrt(time/rank);
        }
        return totalCar>=cars;
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)

👋 Kindness is contagious

Engage with a wealth of insights in this thoughtful article, valued within the supportive DEV Community. Coders of every background are welcome to join in and add to our collective wisdom.

A sincere "thank you" often brightens someone’s day. Share your gratitude in the comments below!

On DEV, the act of sharing knowledge eases our journey and fortifies our community ties. Found value in this? A quick thank you to the author can make a significant impact.

Okay