093. Car Pooling Capacity

Why this mechanism works

Trips contribute weighted boundary deltas rather than unit events. Summing those deltas gives current occupancy. Half-open ordering matters: a seat released at an endpoint is immediately available to a trip starting at that same point.

State and boundaries

active is current passenger occupancy. Events carry passenger-count changes, with negative drop-offs preceding positive pickups at ties.

Protocol

1. Create pickup and drop-off events.
2. Sort by location and delta.
3. Apply each occupancy change.
4. Reject immediately if active exceeds capacity.
5. Accept after all events.

Visualization

2 passengers [1,5)
3 passengers [5,7)
at 5: release 2, then board 3
capacity 3 is sufficient

Python implementation

def car_pooling(trips, capacity):
    events = []
    for passengers, start, end in trips:
        if start < end:
            events.extend(((start, passengers), (end, -passengers)))
    active = 0
    for location, delta in sorted(events):
        active += delta
        if active > capacity:
            return False
    return True

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 car_pooling: events = []
trips=[(2, 1, 5), (3, 3, 7)]; capacity=4; events=[]

L3 car_pooling: for passengers, start, end in trips:
trips=[(2, 1, 5), (3, 3, 7)]; capacity=4; events=[]; passengers=2; start=1; end=5

L5 car_pooling: events.extend(((start, passengers), (end, -passengers)))
trips=[(2, 1, 5), (3, 3, 7)]; capacity=4; events=[(1, 2), (5, -2)]; passengers=2; start=1; end=5

L3 car_pooling: for passengers, start, end in trips:
trips=[(2, 1, 5), (3, 3, 7)]; capacity=4; events=[(1, 2), (5, -2)]; passengers=3; start=3; end=7

L5 car_pooling: events.extend(((start, passengers), (end, -passengers)))
trips=[(2, 1, 5), (3, 3, 7)]; capacity=4; events=[(1, 2), (5, -2), (3, 3), (7, -3)]; passengers=3; start=3; end=7

L6 car_pooling: active = 0
trips=[(2, 1, 5), (3, 3, 7)]; capacity=4; events=[(1, 2), (5, -2), (3, 3), (7, -3)]; passengers=3; start=3; end=7; active=0

L7 car_pooling: for location, delta in sorted(events):
trips=[(2, 1, 5), (3, 3, 7)]; capacity=4; events=[(1, 2), (5, -2), (3, 3), (7, -3)]; passengers=3; start=3; end=7; active=0; location=1; delta=2

L8 car_pooling: active += delta
trips=[(2, 1, 5), (3, 3, 7)]; capacity=4; events=[(1, 2), (5, -2), (3, 3), (7, -3)]; passengers=3; start=3; end=7; active=2; location=1; delta=2

L7 car_pooling: for location, delta in sorted(events):
trips=[(2, 1, 5), (3, 3, 7)]; capacity=4; events=[(1, 2), (5, -2), (3, 3), (7, -3)]; passengers=3; start=3; end=7; active=2; location=3; delta=3

L8 car_pooling: active += delta
trips=[(2, 1, 5), (3, 3, 7)]; capacity=4; events=[(1, 2), (5, -2), (3, 3), (7, -3)]; passengers=3; start=3; end=7; active=5; location=3; delta=3

L2 car_pooling: events = []
trips=[(2, 1, 5), (3, 5, 7)]; capacity=3; events=[]

L3 car_pooling: for passengers, start, end in trips:
trips=[(2, 1, 5), (3, 5, 7)]; capacity=3; events=[]; passengers=2; start=1; end=5

L5 car_pooling: events.extend(((start, passengers), (end, -passengers)))
trips=[(2, 1, 5), (3, 5, 7)]; capacity=3; events=[(1, 2), (5, -2)]; passengers=2; start=1; end=5

L3 car_pooling: for passengers, start, end in trips:
trips=[(2, 1, 5), (3, 5, 7)]; capacity=3; events=[(1, 2), (5, -2)]; passengers=3; start=5; end=7

L5 car_pooling: events.extend(((start, passengers), (end, -passengers)))
trips=[(2, 1, 5), (3, 5, 7)]; capacity=3; events=[(1, 2), (5, -2), (5, 3), (7, -3)]; passengers=3; start=5; end=7

L6 car_pooling: active = 0
trips=[(2, 1, 5), (3, 5, 7)]; capacity=3; events=[(1, 2), (5, -2), (5, 3), (7, -3)]; passengers=3; start=5; end=7; active=0

L7 car_pooling: for location, delta in sorted(events):
trips=[(2, 1, 5), (3, 5, 7)]; capacity=3; events=[(1, 2), (5, -2), (5, 3), (7, -3)]; passengers=3; start=5; end=7; active=0; location=1; delta=2

L8 car_pooling: active += delta
trips=[(2, 1, 5), (3, 5, 7)]; capacity=3; events=[(1, 2), (5, -2), (5, 3), (7, -3)]; passengers=3; start=5; end=7; active=2; location=1; delta=2

... 2 intermediate state changes omitted ...

L7 car_pooling: for location, delta in sorted(events):
trips=[(2, 1, 5), (3, 5, 7)]; capacity=3; events=[(1, 2), (5, -2), (5, 3), (7, -3)]; passengers=3; start=5; end=7; active=0; location=5; delta=3

L8 car_pooling: active += delta
trips=[(2, 1, 5), (3, 5, 7)]; capacity=3; events=[(1, 2), (5, -2), (5, 3), (7, -3)]; passengers=3; start=5; end=7; active=3; location=5; delta=3

L7 car_pooling: for location, delta in sorted(events):
trips=[(2, 1, 5), (3, 5, 7)]; capacity=3; events=[(1, 2), (5, -2), (5, 3), (7, -3)]; passengers=3; start=5; end=7; active=3; location=7; delta=-3

L8 car_pooling: active += delta
trips=[(2, 1, 5), (3, 5, 7)]; capacity=3; events=[(1, 2), (5, -2), (5, 3), (7, -3)]; passengers=3; start=5; end=7; active=0; location=7; delta=-3

Why the solution is correct

Every trip contributes its passenger count exactly throughout its occupied range. The sweep therefore measures actual occupancy at every change point. Capacity is respected everywhere exactly when no event state exceeds it.

Time and space

O(t log t) time and O(t) space for t trips.

Common mistakes

Comparing each trip's passengers separately misses overlapping demand. Pickup-before-drop-off ordering can falsely reject capacity-feasible schedules.

Reasoning card

Transfer exercise

Return the minimum required capacity and the first location where it is reached.