The Number of Passengers in Each Bus II - Problem

You are given two tables: Buses and Passengers.

The Buses table contains information about buses arriving at the LeetCode station, including their bus_id, arrival_time, and capacity (number of empty seats).

The Passengers table contains information about passengers arriving at the station with their passenger_id and arrival_time.

Bus Assignment Rules:

  • A passenger can board a bus if the passenger's arrival time is less than or equal to the bus's arrival time
  • Passengers board the earliest available bus that they are eligible for
  • Each bus has a limited capacity - if more passengers are waiting than the bus can hold, only the first capacity passengers (by arrival time) will board
  • Once a passenger boards a bus, they cannot board another bus

Write a SQL query to find the number of passengers that boarded each bus. Return the result ordered by bus_id in ascending order.

Table Schema

Buses
Column Name Type Description
bus_id PK int Unique identifier for each bus
arrival_time int Time when the bus arrives at the station
capacity int Number of empty seats available on the bus
Primary Key: bus_id
Passengers
Column Name Type Description
passenger_id PK int Unique identifier for each passenger
arrival_time int Time when the passenger arrives at the station
Primary Key: passenger_id

Input & Output

Example 1 — Basic Bus Assignment
Input Tables:
Buses
bus_id arrival_time capacity
1 4 1
3 5 2
Passengers
passenger_id arrival_time
11 1
12 2
13 6
Output:
bus_id passengers_cnt
1 1
3 1
💡 Note:

Passenger 11 arrives at time 1 and can board bus 1 (arrives at time 4). Passenger 12 arrives at time 2 and can board bus 3 (arrives at time 5) since bus 1 is full. Passenger 13 arrives at time 6, after both buses have left, so cannot board any bus.
Example 2 — Empty Bus
Input Tables:
Buses
bus_id arrival_time capacity
1 3 2
2 6 1
Passengers
passenger_id arrival_time
11 7
Output:
bus_id passengers_cnt
1 0
2 0
💡 Note:

Passenger 11 arrives at time 7, which is after both buses have already left (bus 1 at time 3, bus 2 at time 6). Therefore, no passengers board any bus.

Constraints

  • 1 ≤ Buses.bus_id, Passengers.passenger_id ≤ 1000
  • 1 ≤ Buses.arrival_time, Passengers.arrival_time ≤ 1000000
  • 1 ≤ Buses.capacity ≤ 1000000
  • All bus_id values are unique
  • All passenger_id values are unique
  • No two buses arrive at the same time

Visualization

Tap to expand
Passengers in Each Bus II INPUT Buses Table bus_id arrival capacity 1 2 1 2 4 10 3 7 2 Passengers Table pass_id arrival 11 1 12 1 13 5 14 5 B1 B2 B3 ALGORITHM STEPS 1 Sort Both Tables Sort by arrival time ASC 2 Process Each Bus In order of arrival time 3 Board Passengers Until capacity or none left 4 Track Running Sum Remove boarded passengers Processing Timeline t=2 t=4 t=7 P11,P12 P13,P14 cap=1 cap=10 cap=2 1 boards 3 boards 0 boards FINAL RESULT Output Table bus_id passengers 1 1 2 3 3 0 Boarding Summary Bus 1 1 passenger Bus 2 3 passengers Bus 3 0 passengers OK - Total: 4 passengers boarded Key Insight: Greedy approach with running sum: Process buses chronologically. For each bus, board waiting passengers (arrival time less than or equal bus arrival) up to capacity. Use window function SUM() OVER to track cumulative passengers and LAG() to carry forward remaining passenger count between buses. TutorialsPoint - The Number of Passengers in Each Bus II | Optimal Solution

Related Problems

Asked in
Amazon 15 Microsoft 12 Apple 8
12.5K Views
Medium Frequency
~25 min Avg. Time
485 Likes
Ln 1, Col 1
Smart Actions
💡 Explanation
AI Ready
💡 Suggestion Tab to accept Esc to dismiss
// Output will appear here after running code
Code Editor Closed
Click the red button to reopen