1094. Car Pooling - Explanation
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 a integer array trips where trips[i] = [numPassengers[i], from[i], to[i]] indicates that the ith 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.
Example 1:
Input: trips = [[4,1,2],[3,2,4]], capacity = 4
Output: trueExample 2:
Input: trips = [[2,1,3],[3,2,4]], capacity = 4
Output: falseConstraints:
1 <= trips.length <= 1000trips[i].length == 31 <= numPassengers[i] <= 1000 <= from[i] < to[i] <= 10001 <= capacity <= 100,000
Topics
Prerequisites
Before attempting this problem, you should be comfortable with:
- Sorting - Sorting events or intervals by start/end points
- Min-Heap (Priority Queue) - Efficiently tracking and removing minimum elements
- Line Sweep / Difference Array - Processing interval changes as discrete events
1. Brute Force
Intuition
At each pickup location, we need to know how many passengers are currently in the car. We can sort trips by their start location and for each trip, check all previous trips that have not yet dropped off their passengers. If the total exceeds capacity at any point, carpooling is not possible.
Algorithm
- Sort all trips by their pickup location (start time).
- For each trip at index
i:- Start with the number of passengers from the current trip.
- Check all previous trips (
j<i) and add their passengers if their drop-off location is after the current pickup location. - If the total passengers exceed capacity, return
false.
- If all trips pass the capacity check, return
true.
class Solution:
def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
trips.sort(key=lambda x: x[1])
for i in range(len(trips)):
curPass = trips[i][0]
for j in range(i):
if trips[j][2] > trips[i][1]:
curPass += trips[j][0]
if curPass > capacity:
return False
return TrueTime & Space Complexity
- Time complexity:
- Space complexity: or depending on the sorting algorithm.
2. Min-Heap
Intuition
When we process trips in order of pickup time, we only care about trips whose passengers are still in the car. A min-heap ordered by drop-off time lets us efficiently remove all trips whose passengers have already been dropped off before the current pickup. This way, we maintain a running count of current passengers.
Algorithm
- Sort trips by their pickup location.
- Use a min-heap to track active trips, ordered by their drop-off location.
- For each trip:
- Pop all trips from the heap whose drop-off location is at or before the current pickup, subtracting their passengers from the count.
- Add the current trip's passengers to the count.
- If the count exceeds capacity, return
false. - Push the current trip (drop-off time, passenger count) onto the heap.
- Return
trueif all trips are processed without exceeding capacity.
class Solution:
def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
trips.sort(key=lambda t: t[1])
minHeap = [] # pair of [end, numPassengers]
curPass = 0
for numPass, start, end in trips:
while minHeap and minHeap[0][0] <= start:
curPass -= heapq.heappop(minHeap)[1]
curPass += numPass
if curPass > capacity:
return False
heapq.heappush(minHeap, [end, numPass])
return TrueTime & Space Complexity
- Time complexity:
- Space complexity:
3. Line Sweep - I
Intuition
Think of each trip as two events: passengers getting on at the start and passengers getting off at the end. By treating pickups as positive changes and drop-offs as negative changes, we can process all events in sorted order. At any point, if the cumulative passenger count exceeds capacity, the answer is false.
Algorithm
- Create a list of events: (location, +passengers) for pickups and (location, -passengers) for drop-offs.
- Sort events by location. If two events have the same location, process drop-offs (negative) before pickups to handle edge cases correctly.
- Iterate through events, maintaining a running passenger count.
- If the count ever exceeds capacity, return
false. - Return
trueafter processing all events.
class Solution:
def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
points = []
for passengers, start, end in trips:
points.append([start, passengers])
points.append([end, -passengers])
points.sort()
curPass = 0
for point, passengers in points:
curPass += passengers
if curPass > capacity:
return False
return TrueTime & Space Complexity
- Time complexity:
- Space complexity:
4. Line Sweep - II
Intuition
Instead of sorting events, we can use an array where each index represents a location on the route. We record passenger changes at each location: add passengers at pickup points and subtract at drop-off points. A single pass through this array gives us the passenger count at each location.
Algorithm
- Find the range of locations (leftmost pickup to rightmost drop-off).
- Create an array of size (range + 1) initialized to zero.
- For each trip, add passengers at the pickup index and subtract at the drop-off index.
- Iterate through the array, accumulating the passenger count.
- If the count ever exceeds capacity, return
false. Otherwise, returntrue.
class Solution:
def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
L, R = float("inf"), float("-inf")
for _, start, end in trips:
L = min(L, start)
R = max(R, end)
N = R - L + 1
passChange = [0] * (N + 1)
for passengers, start, end in trips:
passChange[start - L] += passengers
passChange[end - L] -= passengers
curPass = 0
for change in passChange:
curPass += change
if curPass > capacity:
return False
return TrueTime & Space Complexity
- Time complexity:
- Space complexity:
Where is the size of the array and is the difference between the rightmost location and the leftmost location.
Common Pitfalls
Not Processing Drop-offs Before Pickups at Same Location
When a passenger is dropped off and another is picked up at the same location, the drop-off must happen first. Failing to sort events so that drop-offs (negative values) come before pickups at the same location causes false capacity violations.
# Wrong: no tiebreaker for same location
points.sort(key=lambda x: x[0])
# Correct: drop-offs (negative) before pickups at same location
points.sort(key=lambda x: (x[0], x[1]))Checking Passengers Still in Car at Drop-off Location
Passengers are dropped off at the end location and are not in the car during that location. A common mistake is including passengers who should have already exited, leading to overcounting.
# Wrong: includes passengers still at drop-off
if trips[j][2] >= trips[i][1]:
# Correct: only count if drop-off is strictly after pickup
if trips[j][2] > trips[i][1]:Off-by-One Error in Difference Array Index
When using a difference array, failing to account for the offset between actual locations and array indices causes incorrect passenger counts. This is especially problematic when locations do not start at zero.
# Wrong: assumes locations start at 0
passChange[start] += passengers
passChange[end] -= passengers
# Correct: adjust for minimum location offset
passChange[start - L] += passengers
passChange[end - L] -= passengers
Sign in to join the discussion