Can one car carry every trip without going over capacity? Mark pickups and drop-offs on a difference array, then sweep the running total.
▼The problem
LeetCode 1094 (Medium). A car with capacity empty seats drives east only. trips[i] = [numPassengers, from, to]: that many passengers get on at kilometre from and off at kilometre to. Return true if every trip can be taken without ever having more than capacity passengers on board.
Examples (LeetCode's): trips = [[2,1,5],[3,3,7]], capacity = 4 → false (between km 3 and 5 both trips ride: 2 + 3 = 5 > 4; walked through in scene 6), and the same trips with capacity = 5 → true (on board after each km: 0 2 2 5 5 3 3 0, never above 5).
The solution
def carPooling(trips, capacity):
change = [0] * 1001
for n, start, end in trips:
change[start] += n
change[end] -= n
riders = 0
for d in change:
riders += d
if riders > capacity:
return False
return TrueTranscript
Car Pooling. A van with a few seats drives east only. Each trip: how many riders, where they get on, and where they get off. Can the van take every trip without going over capacity?
Two trips: two riders from kilometre one to five, and three riders from three to seven. With four seats, five riders share the road between three and five, so it's false. With five seats, it's true.
The naive way stops at every kilometre and adds up every trip that covers it. That's n trips times L kilometres: a thousand trips on a thousand kilometres is a million sums.
Better: only the stops matter. At each pickup, write plus the riders. At each drop-off, write minus. Then drive east once with a running total. If it ever passes capacity, return false. Where three get off and three get on, the change is zero: drop-offs come first.
In code, keep a list of a thousand and one changes. Add riders at the start, subtract them at the end. Then sweep: add each change to the riders on board, and return false if it's too many.
Let's walk it with four seats. Kilometre one: plus two, two on board. Kilometre three: plus three, five on board. Five is more than four: false. With five seats, kilometre five drops two, leaving three, and kilometre seven drops three. Never over: true.
One pass over the trips and one over the road: order n plus L time, and order L space.
Plus at pickup, minus at drop-off, one sweep east. That's Car Pooling.