Show problems as
Classic problem #1094MediumArraySortingHeap (Priority Queue)SimulationPrefix Sum

Car Pooling

Real-world version: One-Way Tram Capacity Check
Tracked in this browser only
Read Car Pooling on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A heritage tram makes one run along a line of numbered stops, starting at stop 0 and always moving to higher-numbered stops. It never doubles back.

bookings[i] = [party, board, leave] is a reserved party of party people who get on at stop board and get off at stop leave, with leave always after board. The tram is built to hold seats people at any one moment.

At a stop, everyone getting off steps down before anyone gets on, so a party that leaves at a stop hands its space to a party boarding at that same stop.

Return true when the single run can carry every reserved party, and false when some stretch of the line would put more than seats people on board.

Examples

Example 1

Input
bookings = [[2, 1, 5], [3, 5, 7]], seats = 3
Output
true

The party of 2 rides from stop 1 and steps down at stop 5, where the party of 3 gets on, so the tram carries 2 people and then 3, never above 3.

Example 2

Input
bookings = [[2, 1, 5], [3, 3, 7]], seats = 4
Output
false

From stop 3 to stop 5 both parties are on board at once, which is 5 people in a tram built for 4.

Example 3

Input
bookings = [[4, 0, 2], [4, 2, 4], [4, 4, 6]], seats = 4
Output
true

Each party steps down at the very stop where the next one gets on, so the tram carries 4 people on each leg of the run.

Constraints

  • 1 <= bookings.length <= 1000
  • bookings[i].length == 3
  • 1 <= party_i <= 100
  • 0 <= board_i < leave_i <= 1000
  • 1 <= seats <= 10^5

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def tram_run_fits(bookings: list[list[int]], seats: int) -> bool:
Java
public boolean tramRunFits(int[][] bookings, int seats)

More on the same topics