NeetCode #545LC-1094MediumHeap / Priority QueueNC 250
← Back to All Problems#545 · #1094 · Car Pooling(拼车)
📌 Problem Statement & Constraints
A car travels east;
trips[i] = [numPassengers, from, to] describes a trip. Given capacity, return whether all trips can be completed without exceeding it. Constraints: 1 <= trips.length <= 1000, 0 <= from < to <= 1000, 1 <= capacity <= 10^5.💡 Core Algorithmic Approaches
- This is a classic difference array problem: passengers get on at
fromand off atto. - Add
numatfromand subtractnumatto, then take the prefix sum. - The maximum of the prefix sum is the peak occupancy, which must not exceed
capacity. - The coordinates are bounded by 1000, so a plain array works and is O(max coordinate + trips).
💻 Benchmark Python3 Implementation
class Solution:
def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
diff = [0] * 1001 # coordinates are at most 1000
for num, frm, to in trips:
diff[frm] += num # passengers board
diff[to] -= num # passengers leave
cur = 0
for x in diff:
cur += x
if cur > capacity:
return False # exceeded at some point
return True⚡ Complexity Deep Dive
⏱️ Time Complexity
O(max coordinate + trips): the sweep is over the fixed coordinate range.
💾 Space Complexity
O(max coordinate) for the difference array.
⚠️ Interview Pitfalls & Follow-ups
- Using an inclusive end: passengers leave before the
topoint, so the subtraction goes atto, notto + 1. - Checking only the trip endpoints: the peak could occur in between, so the whole sweep must be checked.
- Sorting events and using a heap: workable but unnecessary given the bounded coordinates.
- Forgetting that trips may overlap arbitrarily: the prefix sum handles that automatically.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.