Car Pooling

Problem Description

There is a car with capacity empty seats. 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] = [numPassengersi, fromi, toi] indicates that the ith trip has numPassengersi passengers and the passengers must be picked up from fromi and dropped off at toi. The locations are given as the number of kilometers due east from the car’s initial location.

Return true if it is possible to pick up and drop off all passengers for all the given trips, or false otherwise.

Examples

Constraints

• 1 ≤ trips.length ≤ 1000
• trips[i].length == 3
• 1 ≤ numPassengersi ≤ 100
• 0 ≤ fromi < toi ≤ 1000
• 1 ≤ capacity ≤ 10⁵

The Event Line

Passengers enter at from and exit at to. You only care whether the car is ever over capacity at any point. This is a “can you sweep a timeline” problem.

Approach 1 (Difference Array): since locations are bounded to 1000, maintain a 1001-length array. For each trip, add numPassengers at from and subtract at to. Then take a prefix sum and check if any point exceeds capacity.

Approach 2 (Min-Heap): sort trips by pickup location. Process trips in order. Use a min-heap sorted by dropoff to track active passengers. When you reach a new pickup, first drop off everyone with dropoff ≤ current location, then pick up the new passengers. Check if total exceeds capacity.

Solution 1: Difference Array (Simplest)

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        int[] stops = new int[1001]; // locations bounded to [0, 1000]

        for (int[] trip : trips) {
            stops[trip[1]] += trip[0]; // passengers get on
            stops[trip[2]] -= trip[0]; // passengers get off
        }

        int current = 0;
        for (int passengers : stops) {
            current += passengers;
            if (current > capacity) return false;
        }
        return true;
    }
}

class Solution:
    def carPooling(self, trips: list[list[int]], capacity: int) -> bool:
        stops = [0] * 1001

        for num, start, end in trips:
            stops[start] += num
            stops[end] -= num

        current = 0
        for change in stops:
            current += change
            if current > capacity:
                return False
        return True

#include <vector>

class Solution {
public:
    bool carPooling(std::vector<std::vector<int>>& trips, int capacity) {
        std::vector<int> stops(1001, 0);

        for (auto& trip : trips) {
            stops[trip[1]] += trip[0];
            stops[trip[2]] -= trip[0];
        }

        int current = 0;
        for (int change : stops) {
            current += change;
            if (current > capacity) return false;
        }
        return true;
    }
};

Complexity Analysis:

• Time Complexity: O(n + m) where n is the number of trips and m = 1001 (max location).
• Space Complexity: O(m) = O(1001) = O(1).

Where it breaks: the difference array works because locations are bounded to 1000. If locations could be arbitrary large integers, you’d need to coordinate-compress or use the sorting + heap approach instead.

Solution 2: Min-Heap Event Sweep

import java.util.*;

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        Arrays.sort(trips, (a, b) -> a[1] - b[1]); // sort by pickup location
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[2] - b[2]); // min by dropoff

        int current = 0;
        for (int[] trip : trips) {
            // drop off everyone whose dropoff <= current pickup
            while (!heap.isEmpty() && heap.peek()[2] <= trip[1]) {
                current -= heap.poll()[0];
            }
            current += trip[0]; // pick up new passengers
            if (current > capacity) return false;
            heap.offer(trip);
        }
        return true;
    }
}

import heapq

class Solution:
    def carPooling(self, trips: list[list[int]], capacity: int) -> bool:
        trips.sort(key=lambda t: t[1])  # sort by pickup
        heap = []  # (dropoff, num_passengers)
        current = 0

        for num, start, end in trips:
            while heap and heap[0][0] <= start:
                current -= heapq.heappop(heap)[1]
            current += num
            if current > capacity:
                return False
            heapq.heappush(heap, (end, num))

        return True

#include <vector>
#include <queue>
#include <algorithm>

class Solution {
public:
    bool carPooling(std::vector<std::vector<int>>& trips, int capacity) {
        std::sort(trips.begin(), trips.end(), [](const auto& a, const auto& b) {
            return a[1] < b[1];
        });

        // min-heap: {dropoff, num_passengers}
        std::priority_queue<std::pair<int,int>, std::vector<std::pair<int,int>>,
                            std::greater<>> heap;
        int current = 0;

        for (auto& trip : trips) {
            while (!heap.empty() && heap.top().first <= trip[1]) {
                current -= heap.top().second;
                heap.pop();
            }
            current += trip[0];
            if (current > capacity) return false;
            heap.push({trip[2], trip[0]});
        }
        return true;
    }
};

Complexity Analysis:

• Time Complexity: O(n log n) for sorting and heap operations.
• Space Complexity: O(n) for the heap.

Where it breaks: the dropoff condition is <= trip[1], not < trip[1]. Passengers who drop off exactly at the pickup location of the next trip should be removed before counting the new passengers. Getting this wrong (using strict <) would count the departing passengers as still present.

Common Mistakes

• Adding dropoff count at to - 1 instead of to. Passengers exit at to, so the car is free at to. The difference array correctly handles this by subtracting at exactly to.
• Using < instead of <= in the heap dropoff check. Passengers who depart at the same location as an incoming pickup have already left.

Frequently Asked Questions

Why does the difference array subtract at to and not to - 1? Passengers are dropped off at to, meaning they exit before the car is at to. The capacity is freed at exactly location to.

When would you prefer the heap over the difference array? When locations are not bounded (could be any large integers). The difference array requires a fixed-size array bounded by the max location.

← All Problems