DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Car Pooling

mediumGreedy Must-do

Problem statement

A vehicle with capacity empty seats drives in one direction only (east) along a road. You get a list trips, where trips[i] = [passengers, from, to] means that many passengers board at kilometre from and leave at kilometre to. Passengers leaving at a point get off before anyone boards there.

Return true if the vehicle can carry every trip without ever having more than capacity passengers on board, and false otherwise.

Examples

Example 1

Input: trips = [[3, 1, 4], [2, 2, 6], [4, 4, 7]], capacity = 5

Output: false

Explanation: Between km 2 and 4 there are 3 + 2 = 5 on board. At km 4 the first group leaves and 4 board, making 2 + 4 = 6.

Example 2

Input: trips = [[3, 1, 4], [2, 2, 6], [4, 4, 7]], capacity = 6

Output: true

Explanation: The peak load is 6, which fits.

Hints

Approach

Difference array, when locations are small non-negative integers (as in the usual version of this problem, where they stay within a few thousand).

  1. Make an array delta of size max(to) + 1, all zeros.
  2. For each trip, delta[from] += passengers and delta[to] -= passengers.
  3. Walk delta from left to right keeping a running sum. That sum is the load on the stretch starting at each kilometre. If it ever exceeds capacity, return false.

Because each drop-off and pickup at the same kilometre land in the same cell, they cancel correctly with no ordering rule. L is the largest location. When L is bounded this beats sorting; when locations can be huge, use the sweep line.

ComplexityTime O(n + L)Space O(L)
Python
class Solution:
def carPooling(self, trips: list[list[int]], capacity: int) -> bool:
delta = [0] * (max(end for _, _, end in trips) + 1)
for p, start, end in trips:
delta[start] += p
delta[end] -= p
load = 0
for change in delta:
load += change
if load > capacity:
return False
return True

Follow-up questions

  • Return the maximum load reached, and the first kilometre where it happens.
  • Trips arrive one at a time and each must be accepted or rejected immediately. How would you support that efficiently?

Frequently asked questions

Because the statement says passengers leave before anyone boards there. With the opposite order, [[2, 0, 3], [3, 3, 5]] with capacity 3 would briefly count 5 on board at km 3 and wrongly return false.

It is peak concurrency over intervals: given job start and end times, do you ever exceed the worker pool? Given connection open and close timestamps, what is the peak number of open connections? Given reservations, does a cluster ever go over its quota? The event sweep is the standard answer to all of them.