Car Pooling

Car Pooling: the approach in brief

The problem

Implement Solution.carPooling to determine whether one vehicle can complete every requested trip while respecting its passenger capacity. The vehicle travels only east, so locations are ordered along a single route.

Pattern

Car Pooling is a Greedy Patterns problem, in the Line Sweep subpattern. The pattern covers interval scheduling, jump games, stock trading, and task scheduling

Approach outline

1. Think of each trip as adding passengers at its starting location and removing them at its destination.
2. The passenger count changes only at trip endpoints, so there is no need to inspect every point along the road.
3. Process endpoint changes in increasing location order and maintain a running passenger total.

Complexity

The reference solution runs in O(trips.length + 1000) time and O(1000) space.