Parking Dilemma
123456789101112131415161718192021222324252627282930313233343536373839
// There are many cars parked in the parking lot.
// The parking is a straight very long line and a parking slot for every single meter.
// There are cars parked currently and you want to cover them from the rain by building a roof.
// The requirement is that at least k cars are covered by the roof.
// What's the minium length of the roof that would cover k cars?
const cars = [6,2,12,7];
const cars2 = [1,2,3,5,4,8,6,2];
const cars3 = [95,64,43,16,31,58,93,92,49,25,62,5,40];
const k = 5;
// correct - SLIDING WINDOW TECHNIQUE
const carParkingRoof2 = (cars, k) => {
cars.sort((a,b) => a-b);
let maxSumSeen = Infinity;
for (let i=0; i < cars.length; i++) {
if (i >= (k-1)) {
maxSumSeen = Math.min((cars[i] - cars[i-(k-1)]), maxSumSeen);
}
}
return maxSumSeen+1;
};
// VERY WRONG - seem right but wont pass all the tests
const carParkingRoof = (cars, k) => {
//cars.sort((a,b) => a-b);
//console.log(cars)
const noOfLoops = Math.ceil(cars.length / k);
let minLengthOfRoof = Infinity;
for (let i=0; i < noOfLoops; i++) {
minLengthOfRoof = Math.min((cars[i+(k-1)] - cars[i]), minLengthOfRoof);
}
return minLengthOfRoof+1;
};
console.log(carParkingRoof(cars3, k))
console.log(carParkingRoof2(cars3, k))
//console.log(carParkingRoof(cars2, k))
JavaScript
INFO