1094.-car-pooling.md

1094. Car Pooling

• Medium

• There is a car with capacity empty seats. The vehicle only drives east (i.e., it cannot turn around and drive west).

  You are given the integer capacity and an array trips where trip[i] = [numPassengersi, fromi, toi] indicates that the ith trip has numPassengersi passengers and the locations to pick them up and drop them off are fromi and toi respectively. The locations are given as the number of kilometers due east from the car's initial location.

  Return true if it is possible to pick up and drop off all passengers for all the given trips, or false otherwise.

Analysis

The idea is that we create an array to record the number of passengers at every moment on the car. For example, if 2 passengers want to go from 3 to 5. Then we update the array by going to the 3,4 and 5th place and add 2. If, during any moment in the process we find that the current value is larger than capacity, then we return false.

(Since we don't know how long the array should be, we are using a dictionary instead.)

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        need=defaultdict(int) 
        for trip in trips:

            for j in range(trip[1],trip[2]):
                need[j]+=trip[0]

                if need[j]>capacity:
                    return False
        return True

Now since the question has told us that there is on more than 1000 km available, we could create an list of 1001. (0 to 1000)

Then what we put in the array is the number of passengers getting in and out at this place. + for getting in and - for getting out. After setting this, the sum of the values in the array till some point is equal to the current number in the car, if that value is larger than capacity then the car is over-crowded.

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        need=[0]*1001
        for trip in trips:
            need[trip[1]]+=trip[0]
            need[trip[2]]-=trip[0]
        
        for i in need:
            capacity-=i
            if capacity<0:
                return False
        return True