Problem description

You are driving a vehicle that has capacity empty seats initially available for passengers. The vehicle only drives east (ie. it cannot turn around and drive west.)

Given a list of trips, trip[i] = [num_passengers, start_location, end_location] contains information about the i-th trip: the number of passengers that must be picked up, and the locations to pick them up and drop them off. The locations are given as the number of kilometers due east from your vehicle’s initial location.

Return true if and only if it is possible to pick up and drop off all passengers for all the given trips.

Example 1:

Input: trips = [[2,1,5],[3,3,7]], capacity = 4 Output: false Example 2:

Input: trips = [[2,1,5],[3,3,7]], capacity = 5 Output: true Example 3:

Input: trips = [[2,1,5],[3,5,7]], capacity = 3 Output: true Example 4:

Input: trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11 Output: true

Constraints:

trips.length <= 1000 trips[i].length == 3 1 <= trips[i][0] <= 100 0 <= trips[i][1] < trips[i][2] <= 1000 1 <= capacity <= 100000

Solution

If at any location, we need to pickup more passengers than the capacity, we will return False. Otherwise, we return True. Actually, we just need to look at the boundary points, as non boundary points can be coverted to boundary points without changing the number of passengers that need to be picked up.

Below is my python implementation

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        '''
        2     7
              7      9
          3          9
          
        find intersection of inteverals [2, 7) [7, 9) and [3, 9)
        then in each intersection calculate the number of passengers need to pickup. If any of the number is greater than capacity we return False. If all number are smaller than or equal to capacity we return True
        
        Actually, we just need to look at the the boundary points
        '''
        boundaries = set([])
        for trip in trips:
            num, start, end = trip
            boundaries.add(start)
            boundaries.add(end)
        for pos in sorted(boundaries):
            acc = 0
            for trip in trips:
                num, start, end = trip
                if pos >= start and pos < end:
                    acc += num
            if acc > capacity:
                return False
        return True