Greedy - Car Pooling

A car with capacity seats picks up and drops off passengers at various stops. Return if all trips are possible.

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

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

Use a difference array: add passengers at start, remove at end. Scan stops checking capacity.

Create stops array of size 1001
For each trip add passengers at from, subtract at to
Scan stops accumulating passengers
If any point exceeds capacity return false

public boolean carPooling(int[][] trips, int capacity) { int[] stops = new int[1001]; for (int[] trip : trips) { stops[trip[1]] += trip[0]; stops[trip[2]] -= trip[0]; } int passengers = 0; for (int count : stops) { passengers += count; if (passengers > capacity) return false; } return true; }

Time Complexity: O(n)
Space Complexity: O(1)