Problem Statement

Car Pooling

You are driving a car that can hold a limited number of people at once. That limit is the capacity. You get a list of trips. Each trip is three numbers: how many passengers, where they get in (from), and where they get out (to). The car only moves forward, from low numbers to high numbers, like mile markers on a road. Your job is to answer one yes or no question: can you complete every trip without ever having more people in the car than the capacity allows? The trick is to stop thinking about whole trips and start thinking about events. Two kinds of events happen along the road: a pickup, where the car gains passengers, and a dropoff, where the car loses passengers. If you walk down the road in order and add at every pickup and subtract at every dropoff, the running total is exactly how many people are in the car at that moment. If that total ever goes above capacity, the answer is false.

mediumIntervalsSortingIntervalsTime: O(n log n) · Space: O(n)

Signals to notice

enough capacity for all passengers at each stopcumulative passenger countsweep or prefix

Brute force first

Simulate each mile. Extremely slow for long routes. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.

The key insight

Difference array: for each trip, +passengers at start, -passengers at end. Sweep left to right summing — if any position exceeds capacity, return false. or with event sorting. The goal is not to be clever for its own sake, but to remember the one relationship that keeps the solution grounded as you move forward.

Trace it on `trips=[[2,1,5],[3,3,7]], capacity=4`

build events: [2,1,5]→(1,+2),(5,-2); [3,3,7]→(3,+3),(7,-3)
sort by location → events=[(1,+2),(3,+3),(5,-2),(7,-3)]
current=0; process (1,+2) → current=2; 2>4? no
process (3,+3) → current=5; 5>4? YES → return false
answer: false (5 passengers aboard between mile 3 and 5 > capacity 4)

What must stay true

The difference array captures the net change at each position. A prefix sum gives the actual passenger count at each mile. If it ever exceeds capacity, car pooling isn't possible. If that remains true after every update, the rest of the reasoning has a stable place to stand.

Shape of the loop

events = []
for [num, from, to] in trips: events += (from, +num), (to, -num)
sort events by location
current = 0
for (_, change) in events:
    current += change
    if current > capacity: return false
return true

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Not using a difference array — simulating each trip independently or checking each mile directly is much slower. When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.

Intervals Pattern