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;
}
}
Top comments (0)