Validate carpool capacity
Company: Meta
Role: Data Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
##### Question
LeetCode 1094. Car Pooling – Given trips[i] = [numPassengers, start, end] and an integer capacity, return true if the vehicle can fulfill all trips without exceeding capacity at any point; otherwise return false.
https://leetcode.com/problems/car-pooling/description/
Quick Answer: This question evaluates understanding of interval-based resource accounting and algorithmic reasoning with cumulative constraints, assessing skills in processing time-bound events and managing capacity limits.
You are driving a vehicle that has `capacity` empty seats initially available for passengers. The vehicle only drives east (i.e., it cannot turn around and drive west).
You are given the integer `capacity` and an array `trips` where `trips[i] = [numPassengers, start, end]` indicates that the i-th trip has `numPassengers` passengers and the locations to pick them up and drop them off are `start` and `end` respectively. The locations are given as the number of kilometers due east from the vehicle's initial location.
Return `true` if it is possible to pick up and drop off all passengers for all the given trips without exceeding `capacity` at any point along the route, or `false` otherwise.
Note: a passenger occupies a seat over the half-open interval `[start, end)` — they are dropped off exactly at `end`, so a new pickup at the same location as a drop-off does not conflict.
Example:
- Input: trips = [[2,1,5],[3,3,7]], capacity = 4 -> Output: false (between km 3 and 5, 5 passengers are aboard, exceeding capacity 4)
- Input: trips = [[2,1,5],[3,3,7]], capacity = 5 -> Output: true
Constraints
- 1 <= trips.length <= 1000
- trips[i].length == 3
- 1 <= numPassengers <= 100
- 0 <= start < end <= 1000
- 1 <= capacity <= 100000
Examples
Input: ([[2, 1, 5], [3, 3, 7]], 4)
Expected Output: False
Explanation: Between km 3 and 5, both trips overlap: 2 + 3 = 5 passengers aboard, exceeding capacity 4 -> false.
Input: ([[2, 1, 5], [3, 3, 7]], 5)
Expected Output: True
Explanation: Peak occupancy is 5 (km 3-5), which equals capacity 5, so it never exceeds -> true.
Hints
- Think of each trip as +numPassengers at `start` and -numPassengers at `end`. The occupancy only changes at these event points.
- Use a difference array indexed by location: add passengers at `start`, subtract them at `end`. A prefix sum over it gives the number of passengers aboard at every location.
- Sweep the prefix sum from left to right; if it ever exceeds `capacity`, return false. Because drop-off happens exactly at `end`, subtracting at index `end` (not end+1) correctly frees the seat before any same-location pickup.