Car Pooling - Video Solutions

Problem Overview: You receive a list of trips where each trip is [numPassengers, start, end]. A car drives east and cannot turn around. At each location, passengers may get in or out. The goal is to determine whether the car's passenger count ever exceeds its capacity during the journey.

Approach 1: Simulate Passenger Count with Difference Array (Prefix Sum) (Time: O(n + m), Space: O(m))

This approach treats the road as a timeline of passenger changes. For each trip, increment the passenger count at start and decrement it at end. Store these changes in a difference array where each index represents a location. After processing all trips, run a prefix sum across the array to reconstruct the actual passenger count at every point.

The key insight: instead of simulating each trip step‑by‑step, record only where passenger counts change. The prefix sum accumulates those changes efficiently. If the running total ever exceeds capacity, the schedule is impossible. This technique is common in prefix sum and range update problems and works well because the location range is small (≤1000).

Approach 2: Use a Sorted Event List (Sweep Line) (Time: O(n log n), Space: O(n))

This method converts each trip into two events: a pickup event (start, +passengers) and a drop‑off event (end, -passengers). Collect all events and sort them by location. Then sweep from left to right while maintaining the current passenger count.

Whenever you encounter an event, update the running total. Drop‑offs reduce the count, pickups increase it. If the count exceeds capacity at any step, the trips cannot be completed. Sorting ensures events are processed in travel order. This pattern appears frequently in interval problems involving sorting and sweep‑line simulations.

Approach 3: Min‑Heap Trip Simulation (Time: O(n log n), Space: O(n))

Another simulation sorts trips by start location and tracks active trips in a min‑heap keyed by drop‑off location. As the car reaches a new pickup point, remove all trips from the heap whose drop‑off location is ≤ the current start. This frees capacity before boarding new passengers.

Push the current trip into the heap and add its passengers to the running count. If the count exceeds capacity, return false. The heap always holds ongoing trips ordered by the earliest drop‑off. This pattern resembles meeting‑room scheduling using a heap (priority queue).

Recommended for interviews: The difference array (prefix sum) approach is usually considered the cleanest and most optimal because it runs in linear time with minimal logic. The sorted event sweep line is more general and works even when the coordinate range is large. Showing the event simulation first demonstrates understanding of interval processing; presenting the prefix‑sum optimization shows strong algorithmic insight.