Car Pooling

MediumIntervalsprefix sum

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

A car with capacity empty seats drives east only, never turning back. Each entry trips[i] = [numPassengers, from, to] says that group picks up numPassengers people at kilometer from and drops them all off at kilometer to. Passengers who get off at kilometer x leave before anyone boarding at x gets on, so a drop-off and pick-up at the same point never overlap. Return true if every trip can be served without ever having more than capacity passengers in the car, otherwise false.

Examples

Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false
Between km 3 and km 5 there are 5 passengers on board.
Input: trips = [[2,1,5],[3,3,7]], capacity = 5
Output: true
The peak load of 5 fits exactly.
Input: trips = [[2,1,5],[3,5,7]], capacity = 3
Output: true
The first group leaves at km 5 before the second group boards.

Constraints

  • 1 <= trips.length <= 1000
  • trips[i].length == 3
  • 1 <= numPassengers <= 100
  • 0 <= from < to <= 1000
  • 1 <= capacity <= 10^5

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More prefix sum problems