Car Pooling

Problem

Given trips [passengers, from, to] and a car capacity, return true iff the car can complete every trip without exceeding capacity at any point.

Constraints

• 1 ≤ trips.length ≤ 1000
• 0 ≤ from < to ≤ 1000

Approach — Core Patterns

This is a Core Patterns problem. The idea: pick the data structure best matched to the constraints and solve it in one clean pass. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: see the walkthrough below.

Solution code

Python

class Solution:
    def carPooling(self, trips, capacity):
        timeline = [0] * 1001
        for num, start, end in trips:
            timeline[start] += num
            timeline[end] -= num
        cur = 0
        for change in timeline:
            cur += change
            if cur > capacity:
                return False
        return True

Java

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;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.