# 1094 Car Pooling

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 `trips[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.

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
``````

Constraints:

• `1 <= trips.length <= 1000`
• `trips[i].length == 3`
• `1 <= numPassengersi <= 100`
• `0 <= fromi < toi <= 1000`
• `1 <= capacity <= 105`
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 `````` ``````""" Sort timestamp """ class Solution: def carPooling( self, trips: List[List[int]], capacity: int ) -> bool: ts = [] for n, _from, _to in trips: ts.append((_from, n)) ts.append((_to, -n)) ts.sort() occupied = 0 for time, delta in ts: occupied += delta if occupied > capacity: return False return True """ Bucket Sort, Prefix Sum """ class Solution: def carPooling( self, trips: List[List[int]], capacity: int ) -> bool: ts =  * 1001 for n, _from, _to in trips: ts[_from] += n ts[_to] -= n occupied = 0 for delta in ts: occupied += delta if occupied > capacity: return False return True``````