'Minimum car required to accommodate given people
I had one coding round where question statement was like this
*You have a given number of friends and seating capacity of their cars now you need to find minimum number of cars required to accommodate them all.
Example:
People = [1, 4, 1]
SeatingCapacity = [1, 5, 1]
In this case we need minimum 2
cars as number of people on 0th index can adjust with index 1 car.
Example 2:
People = [4, 4, 5, 3]
SeatingCapacity = [5, 5, 7, 3]
This case answer will be as index 3 people can be accommodate into 0,1,2 or 1,2 index car*
I wrote code like this
int numberOfCars(int[] p, int[] s) {
int noOfCars=p.length;
Int extraSeats=0;
for(int i=0;i<p.length;i++) {
extraSeats+= (s[i] - p[i])
}
for(int i=0;i<p.length;i++) {
if(extraSeats-p[i] >=0){
extraSeats-= p[i] ;
noOfCars--;
}
}
return noOfCars;
}
However my code failed for many cases as well as it was saying some performance issue. Can anyone please tell me which cases I missed?
Solution 1:[1]
This can be solved by just greedy approach. Like below:
people = [1,4,1]
p = sum(people) //6
cars = [1,5,1]
sort(cars, descending) //cars = [5,1,1]
idx = 0
while(p > 0) { p -= cars[idx]; idx += 1 }
answer = idx
Handle the corner case where total capacity in cars is less than number of people.
Complexity : sorting cars O(n log n) + while loop O(n) = O(n log n)
Solution 2:[2]
This would be my solution in Javascript:
function peopleCars (persons, seats) {
let numberOfCars = 0;
let people = persons.reduce((previousValue, currentValue) => previousValue + currentValue, 0); //Calculate total number of persons
seats.sort((a,b) => {return b-a}); //Rearrange the total number of seats in each car in ascending order to fill the seats starting from the one that can take the most persons
while(people > 0) {
people -= seats[numberOfCars]; //subtract the numbers of seats of each car from the number of persons available. This will now leave us with the remaining people
numberOfCars += 1 //increment the number of cars to be used.
}
return numberOfCars
}
// console.log (peopleCars( [2,1,2,2], [5,4,2,5]));
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
Solution | Source |
---|---|
Solution 1 | |
Solution 2 |