Car Pooling

medium intervals line sweep

Problem

trips[i] = [numPassengers, from, to]. Given a car capacity, determine whether all trips can be accommodated without ever exceeding capacity. (Drop-off happens at 'to' — that location frees seats.)

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

Outputfalse

At location 3 → 5, the car carries 2 + 3 = 5 passengers; over capacity.

trips (semicolon-separated 'n,from,to')

capacity

def car_pooling(trips, capacity):
    diff = [0] * 1001
    for n, a, b in trips:
        diff[a] += n
        diff[b] -= n
    cur = 0
    for v in diff:
        cur += v
        if cur > capacity:
            return False
    return True

function carPooling(trips, capacity) {
  const diff = new Array(1001).fill(0);
  for (const [n, a, b] of trips) {
    diff[a] += n;
    diff[b] -= n;
  }
  let cur = 0;
  for (const v of diff) {
    cur += v;
    if (cur > capacity) return false;
  }
  return true;
}

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        int[] diff = new int[1001];
        for (int[] t : trips) {
            diff[t[1]] += t[0];
            diff[t[2]] -= t[0];
        }
        int cur = 0;
        for (int v : diff) {
            cur += v;
            if (cur > capacity) return false;
        }
        return true;
    }
}

bool carPooling(vector<vector<int>>& trips, int capacity) {
    vector<int> diff(1001, 0);
    for (auto& t : trips) {
        diff[t[1]] += t[0];
        diff[t[2]] -= t[0];
    }
    int cur = 0;
    for (int v : diff) {
        cur += v;
        if (cur > capacity) return false;
    }
    return true;
}

Explanation

Instead of tracking the car's occupancy mile by mile, we use a difference array (a line sweep): record only the moments passengers get on or off, then add them up as we drive forward.

For each trip [n, a, b] we do diff[a] += n (n people board at a) and diff[b] -= n (they leave at b). Because drop-off frees the seats exactly at b, the minus happens at the same index, so two trips can share that point.

Then we walk the array keeping a running sum cur, which is the number of passengers in the car at that location. If cur ever goes above capacity, the trips can't all fit and we return false.

Example: trips = [[2,1,5],[3,3,7]], capacity = 4. Between locations 3 and 5 both trips overlap, so cur = 2 + 3 = 5, which exceeds 4 and the answer is false.

This works because the prefix sum at any point reflects exactly who is currently on board, and we only need one pass to check it.

Time: O(n + R) Space: O(R)