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 <= 1000trips[i].length == 31 <= numPassengersi <= 1000 <= fromi < toi <= 10001 <= capacity <= 105We can simulate the number of passengers in the car at each kilometer using a difference array. For each trip, increase the passenger count at fromi and decrease it at toi. Then, iterate through this array to calculate the actual number of passengers at each point, checking if it ever exceeds the capacity.
The implementation maintains an array passengerChanges that models changes in the number of passengers at various kilometer points. We iterate over each trip, updating the number of passengers picked up and dropped off. Lastly, we traverse the passengerChanges calculating the current number of passengers and verifying it does not exceed the capacity.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n + m) where n is the number of trips and m is the max distance (1000).
Space Complexity: O(m) for the difference array.
In this approach, we treat each pick-up and drop-off as events. We collect all events, sort them based on location, and then simulate the process of picking up and dropping off passengers by iterating through events in order, checking if it ever exceeds the car's capacity.
We build an array of events, each indicating a change in passenger count, either a pick-up or drop-off, and sort events by time. As we process the events, we update a counter and ensure it never exceeds capacity.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n), driven by sorting events.
Space Complexity: O(n).
| Approach | Complexity |
|---|---|
| Simulate Passenger Count with Difference Array | Time Complexity: O(n + m) where n is the number of trips and m is the max distance (1000). |
| Use a Sorted Event List | Time Complexity: O(n log n), driven by sorting events. |
Car Pooling - Leetcode 1094 - Python • NeetCode • 29,145 views views
Watch 9 more video solutions →Practice Car Pooling with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor