Car Pooling

MEDIUM✓ CHIP-TIMEDLC #1094 — FULL STATEMENT ↗

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.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

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.

EX 01

trips = [[2, 1, 5], [3, 3, 7]] · capacity = 4

→ false

OVERLAPPING TRIPS EXCEED CAPACITY BY ONE

EX 02

trips = [[2, 1, 5], [3, 3, 7]] · capacity = 5

→ true

SAME TRIPS, JUST ENOUGH CAPACITY

EX 03

trips = [[2, 1, 5], [3, 5, 7]] · capacity = 3

→ true

SECOND TRIP STARTS EXACTLY AS THE FIRST ENDS

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 HINTS — TAKE 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 BOARD — THE PATTERN, STEP BY STEP

THE MILE-BY-MILE SWEEPPATTERN · MIN-HEAP OF ACTIVE TRIPStrips [2 riders 1→5] [3 riders 3→7] [4 riders 4→6] · capacity 8

2: 1→5

3: 3→7

4: 4→6

ACTIVE (END, RIDERS) · RUNNING TOTAL

total → 0

STEP 1

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.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/car-pooling.py — RACE PACE

LANG ▸

PACE ▸

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 True

TIME O(N LOG N)SPACE O(N)PYTHON · RACE PACE · 14 LN

class 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 True

TIME O(N + MAXMILE)SPACE O(MAXMILE)PYTHON · TRAINING PACE · 12 LN

class 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;
    }
}

TIME O(N LOG N)SPACE O(N)JAVA · RACE PACE · 21 LN

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;
    }
}

TIME O(N + MAXMILE)SPACE O(MAXMILE)JAVA · TRAINING PACE · 17 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED