Car Pooling
01 · Problem
A car has capacity empty seats and only drives east, so it never turns back. You are given trips, where trips[i] = [numPassengers, from, to] means a group of numPassengers people must be picked up at kilometre from and dropped off at kilometre to (with from < to).
Passengers dropped off at a point leave the car before new passengers are picked up at that same point, so a trip ending at x never overlaps with a trip starting at x.
Return true if the car can complete every trip without ever carrying more than capacity passengers, otherwise return false.
02 · Examples
trips = [[2,1,5],[3,3,7]], capacity = 4
false
Between kilometres 3 and 5 both groups are aboard: 2 + 3 = 5 passengers, which exceeds 4.
trips = [[2,1,5],[3,3,7]], capacity = 5
true
The peak load is 5 between kilometres 3 and 5, which fits exactly.
trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11
true
The group of 3 leaves at kilometre 7 just before the next group of 3 boards there. The peak load is 3 + 8 = 11, which fits.
03 · Constraints
- 011 <= trips.length <= 1000
- 02trips[i].length == 3
- 031 <= numPassengers <= 100
- 040 <= from < to <= 1000
- 051 <= capacity <= 105
04 · Optimal complexity
- Time
- O(k + L)
- Space
- O(L)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.