Car Pooling (LeetCode 1094)

The problem

A car with capacity empty seats drives in one direction. Each trip is [num, start, end]: pick up num passengers at location start and drop them at end. Return True if the car can complete every trip without ever carrying more than capacity people.

Input:  trips = [[2, 1, 5], [3, 3, 7]], capacity = 4
Output: False

Between locations 3 and 5 both groups are in the car: 2 + 3 = 5 passengers, more than 4. With capacity = 5 the answer is True.

How to think about it

Start with brute force. For each location from the first pick-up to the last drop-off, add up the passengers of every trip covering it. With locations up to 1000 and trips up to 1000, that is about 10⁶ steps. It works, but it does not scale with the coordinate range.

The key insight: the load only changes at pick-ups and drop-offs. Record a change at each event instead of the load at each point: +num at start, -num at end. Then walk the event points in order and keep a running sum. That running sum is the load. This is a difference array, which is a prefix sum in reverse: you store the deltas and the prefix sum rebuilds the values.

Drop-offs happen before pick-ups at the same spot. Passengers leave at end, so a trip ending at 5 and one starting at 5 never share the car. Merging both into one delta[5] handles that automatically, because the net change is applied at once.

Which pattern is this? Intervals with a sweep line, the same idea as Meeting Rooms II but with weights. The tell is “intervals with a quantity, and a limit on the total at any moment”.

Approach

1. Build delta: for each trip add num at start and subtract num at end.
2. Walk the locations in sorted order, adding delta[t] to a running cur.
3. If cur ever exceeds capacity, return False.
4. Otherwise return True.

Solution

from collections import defaultdict

def car_pooling(trips, capacity):
    delta = defaultdict(int)
    for num, s, e in trips:
        delta[s] += num; delta[e] -= num     # board at s, leave at e
    cur = 0
    for t in sorted(delta):                  # sweep event points left to right
        cur += delta[t]                      # running sum = passengers in the car
        if cur > capacity: return False
    return True
# car_pooling([[2,1,5],[3,3,7]], 4) -> False
# car_pooling([[2,1,5],[3,3,7]], 5) -> True

Dry run

delta = {1: +2, 5: -2, 3: +3, 7: -3}, swept in order 1, 3, 5, 7.

Complexity

• Time: O(n log n). Up to 2n event points are sorted; the sweep is linear.
• Space: O(n). The delta map. (Because locations are at most 1000, a fixed array of size 1001 also works and gives O(n + 1000) time with no sort.)

Edge cases and pitfalls

• Drop-off and pick-up at the same location ([[2, 1, 5], [3, 5, 7]] with capacity 3) returns True: the -2 and +3 combine at location 5, so the load never goes above 3.
• A single trip larger than capacity returns False at its first event.
• Processing pick-ups before drop-offs at the same point with separate events gives false False answers. Merging deltas per location, as here, avoids that.
• Forgetting the import: defaultdict comes from collections.

Related problems

• Meeting Rooms II (LeetCode 253): the same sweep where every event has weight 1.
• Range Sum Query - Immutable (LeetCode 303): the prefix sum that rebuilds the load from the deltas.
• My Calendar I (LeetCode 729): capacity 1, with bookings arriving one at a time.