Car pooling: check a one-way route never exceeds the seats

A vehicle with a fixed number of seats drives in one direction only. Each trip is [passengers, start, end]: that many people get on at kilometer start and off at kilometer end. Decide whether the vehicle can complete every trip without ever carrying more people than it has seats.

Interface

Unless you agree on a different interface with the interviewer, assume:

• car_pooling(trips: list[list[int]], capacity: int) -> bool — passengers occupy a seat on [start, end), so a drop-off and a pickup at the same kilometer do not overlap.

Example

car_pooling([[2, 1, 5], [3, 3, 7]], 4)              ->  False   # 5 people aboard between km 3 and 5
car_pooling([[2, 1, 5], [3, 3, 7]], 5)              ->  True    # the peak of 5 equals the capacity
car_pooling([[2, 1, 5], [3, 5, 7]], 3)              ->  True    # the first group leaves at km 5 as the second boards
car_pooling([[3, 2, 7], [3, 7, 9], [8, 3, 9]], 11)  ->  True

Constraints

• 1 <= len(trips) <= 1000, 1 <= passengers <= 100, 0 <= start < end <= 1000, 1 <= capacity <= 10^5.

Clarifying questions

• Do people leave before others board at the same kilometer?
• Are the locations small integers, or arbitrary values?
• Are the trips sorted by start?

What a strong answer covers

• A difference array over the kilometers: add passengers at start, subtract at end, then a running sum checked against the capacity. O(n + L) for route length L.
• An event sweep for arbitrary locations: sort (position, change) events with drop-offs before pickups at the same position. O(n log n).
• A heap of current trips ordered by end as another option.
• Tests: touching trips, a single trip over capacity, trips in any order.

Follow-ups

• Return the first kilometer where the capacity is exceeded.
• Find the smallest capacity that works for all trips.
• Trips arrive one at a time. Accept or reject each as it comes.