Intervals - Car Pooling

Given trips where trips[i]=[numPassengers, from, to] and capacity, return true if you can pick up and drop off all passengers without exceeding vehicle capacity at any point.

Input: trips=[[2,1,5],[3,3,7]], capacity=4 → Output: false

Input: trips=[[2,1,5],[3,3,7]], capacity=5 → Output: true

Use a difference array (event-based). At each pickup location add passengers, at dropoff subtract. Scan from left and check if passengers ever exceed capacity.

Create a diff[] array of size 1001 (max stop value).
For each trip: diff[from] += num; diff[to] -= num.
Scan diff[]: if running sum > capacity at any point, return false.

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 d : diff) { cur += d; if (cur > capacity) return false; } return true; } }

Time Complexity: O(N + M) where M=1001
Space Complexity: O(M)