Car Pooling

Problem Statement

Given a list of trips [numPassengers, from, to] and a car with a fixed capacity, determine whether the car can make every pickup and drop-off along the route without ever exceeding capacity.

Input

• trips — each entry [p, s, e] picks up p passengers at location s, drops them off at location e.
• capacity — integer seat capacity.

trips = [[2,1,5],[3,3,7]], capacity = 4

Output

A boolean: true if the trip sequence is feasible, false if capacity is exceeded at any point.

false

Constraints

• 1 ≤ trips.length ≤ 1000
• 0 ≤ trips[i][0] ≤ 100 (passengers per trip)
• 0 ≤ trips[i][1] < trips[i][2] ≤ 1000 (locations)
• 1 ≤ capacity ≤ 10⁵

Intuition

Two interchangeable lenses — both are sweep-line at heart:

• Sweep line: each trip produces a +p event at pickup and a -p event at drop-off. Sort events by location, sweep, reject as soon as the running load exceeds capacity.
• Difference array: because locations are bounded 0…1000, use a fixed array diff[], do diff[s] += p and diff[e] -= p in O(1), then prefix-sum the array to get the load at every point.

diff after updates:  [0, +2, 0, +3, 0, -2, 0, -3, 0, …]
Prefix sums:         [0,  2, 2,  5, 5,  3, 3,  0, …]
                               ↑ exceeds capacity 4 → return false

Solution

def carPooling(trips: list[list[int]], capacity: int) -> bool:
    events = []
    for p, s, e in trips:
        events.append((s, p))
        events.append((e, -p))
 
    events.sort()
    cur = 0
    for _, delta in events:
        cur += delta
        if cur > capacity:
            return False
 
    return True

def carPooling(trips: list[list[int]], capacity: int) -> bool:
    diff = [0] * 1001  # locations 0..1000
    for p, s, e in trips:
        diff[s] += p
        diff[e] -= p
 
    cur = 0
    for d in diff:
        cur += d
        if cur > capacity:
            return False
 
    return True

function carPooling(trips: number[][], capacity: number): boolean {
    const diff = new Array(1001).fill(0);
    for (const [p, s, e] of trips) {
        diff[s] += p;
        diff[e] -= p;
    }
 
    let cur = 0;
    for (const d of diff) {
        cur += d;
        if (cur > capacity) return false;
    }
 
    return true;
}

Complexity

Edge Case Thinking