Car Pooling
Medium · Intervals · Array · Sorting · Prefix Sum · Simulation
Problem
A car with capacity empty seats drives in one direction only (east); it cannot turn around. You are given trips, where trips[i] = [numPassengers, from, to]: that group boards at kilometer from and leaves at kilometer to.
Passengers who leave at a kilometer free their seats before anyone boards there. Return true if every trip can be served without ever exceeding capacity, and false otherwise.
Examples
Input: trips = [[3,1,6],[2,4,8]], capacity = 4 Output: false
Between kilometers 4 and 6 there are 5 passengers on board.
Input: trips = [[3,1,6],[2,6,8]], capacity = 4 Output: true
The first group leaves at 6 just as the second boards, so at most 3 ride at once.
Input: trips = [[1,0,2],[1,1,3],[1,2,4]], capacity = 2 Output: true
Never more than two passengers are in the car.
Constraints
- 1 <= len(trips) <= 1000
- trips[i] = [numPassengers, from, to]
- 1 <= numPassengers <= 100
- 0 <= from < to <= 1000
- 1 <= capacity <= 10^5
Approaches
- Baseline: load at every pick-up — time O(n²), space O(1)
Follow-up
What if the kilometers went up to 10^9? A 10^9-entry array is out of the question, so sort the 2n events (pick-ups and drop-offs, drop-offs first on a tie) and sweep them, or use a sorted map from kilometer to change: O(n log n).
Related problems
Start free on Cariara · Coding problems · System design studio
