Minimum car required to accommodate given people

user_5913407 0
Viewed 1659

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?

data-structures algorithm java
2 Answers

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)

user_24530890

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]));
user_57277730
Related