Car Pooling
The key idea
Only the passenger count *between* stops matters, so turn every trip into a
+passengers event at its pickup km and a -passengers event at its dropoff km. A running sum of those events along the road is the live headcount; if it ever exceeds capacity, a trip cannot be served.Problem
You drive a car that can carry at most capacity passengers, and it only ever moves east (it never turns around).
You are given a list trips, where trips[i] = [numPassengers, from, to] means there are numPassengers riders who get on at kilometer from and get off at kilometer to. The locations are kilometer markers measured east of the start.
Return true if and only if you can pick up and drop off all the passengers for every trip without ever exceeding capacity people in the car at the same time. A group that gets off at a kilometer frees up its seats for a group getting on at that same kilometer.
Constraints
1 <= trips.length <= 1000trips[i].length == 31 <= numPassengers[i] <= 1000 <= from[i] < to[i] <= 10001 <= capacity <= 10^5
Examples
Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false
Input: trips = [[2,1,5],[3,3,7]], capacity = 5
Output: true
Input: trips = [[2,1,5],[3,5,7]], capacity = 3
Output: true
Complexity
Time: O(n + M) Space: O(M)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization