⚡Flashcard Drill➔
NeetCode #545LC-1094MediumHeap / Priority QueueNC 250
← Back to All Problems

#545 · #1094 · Car Pooling(拼车)

📌 Problem Statement & Constraints

A car travels east; trips[i] = [numPassengers, from, to] describes a trip. Given capacity, return whether all trips can be completed without exceeding it. Constraints: 1 <= trips.length <= 1000, 0 <= from < to <= 1000, 1 <= capacity <= 10^5.

💡 Core Algorithmic Approaches

  1. This is a classic difference array problem: passengers get on at from and off at to.
  2. Add num at from and subtract num at to, then take the prefix sum.
  3. The maximum of the prefix sum is the peak occupancy, which must not exceed capacity.
  4. The coordinates are bounded by 1000, so a plain array works and is O(max coordinate + trips).

💻 Benchmark Python3 Implementation

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        diff = [0] * 1001                  # coordinates are at most 1000
        for num, frm, to in trips:
            diff[frm] += num               # passengers board
            diff[to] -= num                # passengers leave
        cur = 0
        for x in diff:
            cur += x
            if cur > capacity:
                return False               # exceeded at some point
        return True

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(max coordinate + trips): the sweep is over the fixed coordinate range.
💾 Space Complexity
O(max coordinate) for the difference array.

⚠️ Interview Pitfalls & Follow-ups

  • Using an inclusive end: passengers leave before the to point, so the subtraction goes at to, not to + 1.
  • Checking only the trip endpoints: the peak could occur in between, so the whole sweep must be checked.
  • Sorting events and using a heap: workable but unnecessary given the bounded coordinates.
  • Forgetting that trips may overlap arbitrarily: the prefix sum handles that automatically.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Heap / Priority Queue Problems