Car Pooling
The briefingthe full drill, in my own words
The drill: A car makes a single loop of pickups and drop-offs — each trip lists its passenger count plus the mile it boards and the mile it gets off — decide whether the car's fixed capacity is ever exceeded along the route.
A car drives a single straight route and picks up or drops off groups of passengers at specific trips, each trip listing a passenger count, a boarding mile, and a drop-off mile.
Passengers from a trip are aboard from their boarding mile up to, but not including, their drop-off mile — the moment a group's drop-off mile is reached, those seats are free again.
The car has a fixed seat capacity, and the task is a single yes-or-no verdict: whether the passenger count ever exceeds that capacity anywhere along the route.
- trip counts run up to a few thousand
- passenger counts per trip and total capacity are positive
- a drop-off mile frees seats before same-mile pickups fill them
- the answer is one boolean covering the whole route
The hintstake only what you need
HINT 1 THE NUDGE
Only two moments matter for each trip: passengers get added at the pickup mile and removed at the drop-off mile — the miles in between never need to be touched individually.
HINT 2 THE STRUCTURE
Sorting trips by pickup mile and sweeping forward turns this into a single pass: at each pickup, first free up any capacity from trips that have already ended.
HINT 3 ONE STEP FROM THE ANSWER
A min-heap of active trips keyed by drop-off mile tells you instantly which passengers to remove before adding new ones — pop everyone whose drop-off is at or before the current pickup, then check if the running total still fits.
Coach's boardthe pattern, step by step
Three trips, capacity 8. Sorted by pickup mile: trip 0 boards 2 at mile 1, trip 1 boards 3 at mile 3, trip 2 boards 4 at mile 4.
The splitstwo paces, two languages
class Solution:
def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
ordered = sorted(trips, key=lambda t: t[1])
heap = [] # (endMile, passengers) for trips currently aboard
current = 0
for num, start, end in ordered:
while heap and heap[0][0] <= start:
_, dropped = heapq.heappop(heap)
current -= dropped
current += num
if current > capacity:
return False
heapq.heappush(heap, (end, num))
return Trueclass Solution:
def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
delta = [0] * 1001
for num, start, end in trips:
delta[start] += num
delta[end] -= num
current = 0
for change in delta:
current += change
if current > capacity:
return False
return Trueclass Solution {
public boolean carPooling(int[][] trips, int capacity) {
int[][] ordered = trips.clone();
Arrays.sort(ordered, (a, b) -> a[1] - b[1]);
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]); // [endMile, passengers]
int current = 0;
for (int[] t : ordered) {
int num = t[0], start = t[1], end = t[2];
while (!heap.isEmpty() && heap.peek()[0] <= start) {
current -= heap.poll()[1];
}
current += num;
if (current > capacity) {
return false;
}
heap.offer(new int[] { end, num });
}
return true;
}
}class Solution {
public boolean carPooling(int[][] trips, int capacity) {
int[] delta = new int[1001];
for (int[] t : trips) {
delta[t[1]] += t[0];
delta[t[2]] -= t[0];
}
int current = 0;
for (int change : delta) {
current += change;
if (current > capacity) {
return false;
}
}
return true;
}
}✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED