Car Pooling

NeetCode: Car Pooling · LeetCode: 1094. Car Pooling · Difficulty: Medium

A car has capacity empty seats and only drives east. You are given trips[i] = [passengers, from, to]: pick up passengers at from and drop them off at to. Return true if all trips can be completed without ever exceeding the capacity.

Passengers dropped off at a stop leave before the passengers picked up at that same stop board.

Example

Text

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

In the first example, between stops 3 and 5 the car holds 2 + 3 = 5 passengers, which is more than 4.

Brute force: simulate every stop

For each stop position, add up the passengers of every trip that is on board there (from <= stop < to). If some stop exceeds the capacity, answer false. The stops range from 0 to maxTo, the largest drop-off position, so with T trips and a maximum position M this is O(M * T).

Java

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        int maxTo = 0;
        for (int[] t : trips) {
            maxTo = Math.max(maxTo, t[2]);
        }
        for (int stop = 0; stop <= maxTo; stop++) {
            int onBoard = 0;
            for (int[] t : trips) {
                if (t[1] <= stop && stop < t[2]) {
                    onBoard += t[0];
                }
            }
            if (onBoard > capacity) {
                return false;
            }
        }
        return true;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.carPooling(new int[][]{{2, 1, 5}, {3, 3, 7}}, 4));
        System.out.println(s.carPooling(new int[][]{{2, 1, 5}, {3, 3, 7}}, 5));
        System.out.println(s.carPooling(new int[][]{}, 1));
        System.out.println(s.carPooling(new int[][]{{3, 2, 4}, {3, 4, 6}}, 3));
    }
}

Output

false
true
true
true

The last case checks the boundary rule: the first group leaves at 4 as the second boards, so 3 seats suffice. Time: O(M * T). Space: O(1).

Better: sort by pickup and keep a min-heap of drop-offs

Only the moments where someone boards can push the load above capacity, so process trips in order of from. Keep the current load and a min-heap keyed by drop-off position. Before boarding a trip, poll every group whose drop-off is at or before this pickup and subtract them from the load. Then add the new group and compare with the capacity. Java's PriorityQueue is a min-heap ordered by the comparator, so a comparator on the drop-off position puts the earliest drop-off on top. The comparator uses Comparator.comparingInt, not a subtraction, which could overflow.

Java

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        int[][] sorted = trips.clone();
        Arrays.sort(sorted, Comparator.comparingInt(t -> t[1]));
        // Each entry is {drop-off position, passengers}. The smallest drop-off is on top.
        PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(e -> e[0]));
        int load = 0;
        for (int[] t : sorted) {
            int passengers = t[0], from = t[1], to = t[2];
            while (!heap.isEmpty() && heap.peek()[0] <= from) {
                load -= heap.poll()[1];
            }
            load += passengers;
            if (load > capacity) {
                return false;
            }
            heap.add(new int[]{to, passengers});
        }
        return true;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.carPooling(new int[][]{{2, 1, 5}, {3, 3, 7}}, 4));
        System.out.println(s.carPooling(new int[][]{{2, 1, 5}, {3, 3, 7}}, 5));
        System.out.println(s.carPooling(new int[][]{}, 1));
        System.out.println(s.carPooling(new int[][]{{3, 2, 4}, {3, 4, 6}}, 3));
    }
}

Output

false
true
true
true

Time: O(T log T) for the sort and the heap operations. Space: O(T).

Optimal: difference array

Record only the changes in load: +passengers at from and -passengers at to. A running prefix sum over positions then gives the load at each stop, and a drop-off at to is applied together with any pickup at to in the same cell, so the boundary rule holds. This is O(T + M) and needs no sorting. The array is indexed by position, so diff[t[1]] needs positions to be non-negative int values, which the constraints guarantee. LeetCode bounds positions by 1000, so M is small; for very large positions the heap approach is better because it does not depend on M.

Java

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        int maxTo = 0;
        for (int[] t : trips) {
            maxTo = Math.max(maxTo, t[2]);
        }
        int[] diff = new int[maxTo + 1];
        for (int[] t : trips) {
            diff[t[1]] += t[0];
            diff[t[2]] -= t[0];
        }
        int load = 0;
        for (int change : diff) {
            load += change;
            if (load > capacity) {
                return false;
            }
        }
        return true;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.carPooling(new int[][]{{2, 1, 5}, {3, 3, 7}}, 4));
        System.out.println(s.carPooling(new int[][]{{2, 1, 5}, {3, 3, 7}}, 5));
        System.out.println(s.carPooling(new int[][]{}, 1));
        System.out.println(s.carPooling(new int[][]{{3, 2, 4}, {3, 4, 6}}, 3));
    }
}

Output

false
true
true
true

Time: O(T + M). Space: O(M).