Does the car pool fit?
Check whether a car with limited seats can carry every trip, by adding passengers at each pick-up and removing them at each drop-off while sweeping through time. About 20 minutes.
Weighted events
A car has a number of seats. Each trip carries some passengers from a pick-up point to a drop-off point along a road. Can the car do all the trips?
This is the earlier sweep with weights. At the pick-up point the passenger count goes up by the trip's passengers. At the drop-off it goes down by the same amount. Passengers dropped at a point leave before new ones board there.
Check the peak
Sort the events by position, and by amount at the same position, so that negative amounts come first. Walk through, adding the amounts to a running load.
If the load ever goes above the number of seats, the answer is no. If you reach the end without that, the answer is yes. Only the highest load matters, not where it occurs.
load += change
if load > seats:
return FalseAt point 1: pick up 2. The load is 2, which is within 5 seats.
Seats 3. One trip carries 3 people from 2 to 4, another carries 3 from 4 to 6. Does it fit?
- AYes
- BNo
- COnly with 6 seats
Show the answer
Yes. At point 4 the first group leaves before the second boards.
Car pooling
A car has capacity empty seats and drives in one direction. You are given trips, where trips[i] = [passengers, from, to]: passengers people board at position from and leave at position to. Return true if the car can complete all the trips without ever carrying more than capacity people. People leave before new ones board at the same position.
trips = [[2, 1, 5], [3, 3, 7]], capacity = 4 → false
0 ≤ trips.length ≤ 100,000 · 1 ≤ passengers ≤ 100 · 0 ≤ from < to ≤ 1,000,000 · 1 ≤ capacity ≤ 100,000