Problem Description
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] = [numPassengers_i, from_i, to_i] indicates that the i-th trip has numPassengers_i passengers and the locations to pick them up and drop them off are from_i and to_i 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.
Key Insights
- The car can only pick up and drop off passengers moving in one direction (east).
- We need to track the number of passengers in the car at any point in time to ensure it does not exceed the capacity.
- Using a timeline approach, we can increment the number of passengers when a pickup occurs and decrement it when a drop-off occurs.
Space and Time Complexity
Time Complexity: O(N + K), where N is the number of trips and K is the maximum distance (1000 in this case). Space Complexity: O(K), where K is the maximum distance (1000).
Solution
To solve the problem, we can utilize a "difference array" approach. We create an array to represent the number of passengers at each kilometer point. For each trip, we increase the count of passengers at the pickup location and decrease it at the drop-off location. After processing all trips, we can iterate through the array to maintain a running total of passengers in the car and check if it exceeds the capacity at any point.