Problem Breakdown
We are tasked with determining if a vehicle can complete a series of trips without exceeding its capacity at any point during the journey. The car moves strictly East, meaning locations increase monotonically from 0 upwards. Each trip specifies how many passengers get on (num_passengers) and off (at end_location).
Inputs:
trips: A list of lists where each inner list is[passengers, start_loc, end_loc].capacity: An integer representing the maximum number of seats.
Output:
- Boolean (
Trueif all trips can be accommodated,Falseotherwise).
Implicit Constraints & Edge Cases:
- Coordinate Range: Locations are integers up to 1000. This suggests a coordinate-based approach (difference array) is viable and efficient compared to sorting events for larger ranges.
- Simultaneous Events: A passenger drops off at
end_locwhile another picks up at the same location. Since they occupy seats on different intervals, we must ensure that capacity isn’t exceeded between these points or during the transition. The standard interpretation is that drop-offs happen before pickups effectively (or net change logic handles it), so processing changes at a specific coordinate index correctly reflects load for subsequent distance. - Empty Input: If
tripsis empty, no passengers are needed; capacity constraint is trivially satisfied (True).
Intuition
A brute-force simulation would involve iterating through every kilometer from the minimum start location to the maximum end location (up to 1000). At each step, we’d check which trips are active. This results in complexity where is trip count and is max distance. While acceptable for small constraints (), it’s inefficient logic-wise because the state only changes at specific event points (start/end locations).
Key Insight: The passenger load on the vehicle only changes when a pickup or drop-off occurs. This transforms the problem into an interval scheduling / sweep-line problem. We can track “net change” in passengers for each location using a difference array. By iterating through these events, we maintain a running sum of current passengers and check against capacity.
Approach
- Initialize Tracking Structure: Create a list (difference array) large enough to cover the maximum end location found in any trip plus one buffer. Initialize with zeros. Given constraints (), an array of size ~1005 is sufficient and efficient.
- Record Changes: Iterate through each
trip. For a trip[num, start, end]:- Add
numto the index corresponding tostart. This represents passengers entering at this location. - Subtract
numfrom the index corresponding toend. This represents passengers leaving (freeing capacity) exactly when they reach their destination. Note: We subtract atend, notend - 1, because once a passenger reachesend, they are no longer occupying seats for any distance beyond that point.
- Add
- Sweep Line Check: Iterate through the difference array from index 0 up to the maximum location encountered (or simply iterate over all populated indices). Maintain a running sum (
current_passengers). - Capacity Validation: At each step, add the change recorded at that location to
current_passengers. Ifcurrent_passengersexceedscapacity, returnFalseimmediately. - Completion: If we finish iterating through all locations without exceeding capacity, return
True.
Complexity Analysis
- Time Complexity: where is the number of trips and is the maximum location value (bounded by 1000). We iterate once to populate changes () and once through the array range (). Given constraints, this effectively behaves as linear time relative to input size.
- Space Complexity: for the difference array where is the maximum location value (1002 in worst case per constraints). This fits easily within memory limits.
Solution
class Solution:
def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
# Determine max end location to size our difference array correctly.
# Constraints say locations <= 1000, but dynamic sizing is safer practice.
if not trips:
return True
max_end = 0
for _, start, end in trips:
max_end = max(max_end, end)
# Difference array to track passenger changes at each location.
# Size needs to be max_end + 1 because we access index 'end'.
diff_array = [0] * (max_end + 2)
for num_passengers, start_loc, end_loc in trips:
diff_array[start_loc] += num_passengers
diff_array[end_loc] -= num_passengers
current_load = 0
# Sweep through locations.
# We iterate up to max_end because that's the furthest point we need to track load for.
# Note: Iterating beyond max_end is unnecessary as no trips end there, but safe to go higher if needed.
for i in range(max_end + 1):
current_load += diff_array[i]
# If at any location the running sum exceeds capacity, it's impossible.
if current_load > capacity:
return False
return True
Edge Cases Handled
- Empty Trips: The loop over
tripswon’t execute; logic implicitly returnsTrue. Added explicit check for clarity in thought process (though code handles it naturally). - Capacity Exactly Met: If load equals capacity, the condition
current_load > capacityis false, so we continue. This correctly allows full utilization of seats. - Drop-off at Same Location as Pick-up: The difference array logic processes both increments and decrements at index
i. Since Python evaluates sequentially in a loop, if multiple events happen at same location (e.g., drop off then pick up), the net change is applied tocurrent_loadbefore checking capacity. This correctly models that passengers leaving free space for those entering simultaneously without violating constraints between intervals. - Large Capacity: Python handles large integers automatically; no overflow issues compared to languages like C++ or Java.