Problem

Table: Buses

+--------------+------+
| Column Name  | Type |
+--------------+------+
| bus_id       | int  |
| arrival_time | int  |
| capacity     | int  |
+--------------+------+
bus_id contains unique values.
Each row of this table contains information about the arrival time of a bus at the LeetCode station and its capacity (the number of empty seats it has).
No two buses will arrive at the same time and all bus capacities will be positive integers.

Table: Passengers

+--------------+------+
| Column Name  | Type |
+--------------+------+
| passenger_id | int  |
| arrival_time | int  |
+--------------+------+
passenger_id contains unique values.
Each row of this table contains information about the arrival time of a passenger at the LeetCode station.

Buses and passengers arrive at the LeetCode station. If a bus arrives at the station at a time tbus and a passenger arrived at a time tpassenger where tpassenger <= tbus and the passenger did not catch any bus, the passenger will use that bus. In addition, each bus has a capacity. If at the moment the bus arrives at the station there are more passengers waiting than its capacity capacity, only capacity passengers will use the bus.

Write a solution to report the number of users that used each bus.

Return the result table ordered by bus_id in ascending order.

The result format is in the following example.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

Input: 
Buses table:
+--------+--------------+----------+
| bus_id | arrival_time | capacity |
+--------+--------------+----------+
| 1      | 2            | 1        |
| 2      | 4            | 10       |
| 3      | 7            | 2        |
+--------+--------------+----------+
Passengers table:
+--------------+--------------+
| passenger_id | arrival_time |
+--------------+--------------+
| 11           | 1            |
| 12           | 1            |
| 13           | 5            |
| 14           | 6            |
| 15           | 7            |
+--------------+--------------+
Output: 
+--------+----------------+
| bus_id | passengers_cnt |
+--------+----------------+
| 1      | 1              |
| 2      | 1              |
| 3      | 2              |
+--------+----------------+
Explanation: 
- Passenger 11 arrives at time 1.
- Passenger 12 arrives at time 1.
- Bus 1 arrives at time 2 and collects passenger 11 as it has one empty seat.
- Bus 2 arrives at time 4 and collects passenger 12 as it has ten empty seats.
- Passenger 12 arrives at time 5.
- Passenger 13 arrives at time 6.
- Passenger 14 arrives at time 7.
- Bus 3 arrives at time 7 and collects passengers 12 and 13 as it has two empty seats.

Solution

Method 1 - Window Functions and Cumulative Assignment

We assign each passenger to the earliest bus they can catch, respecting bus capacity, using window functions and cumulative sums.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

WITH bus_order AS (
  SELECT *, ROW_NUMBER() OVER (ORDER BY arrival_time) AS rn
  FROM Buses
),
passenger_order AS (
  SELECT *, ROW_NUMBER() OVER (ORDER BY arrival_time) AS rn
  FROM Passengers
),
assignments AS (
  SELECT p.passenger_id, b.bus_id, b.arrival_time AS bus_time, b.capacity,
         p.arrival_time AS pass_time,
         ROW_NUMBER() OVER (PARTITION BY b.bus_id ORDER BY p.arrival_time) AS bus_pos
  FROM bus_order b
  JOIN passenger_order p
    ON p.arrival_time <= b.arrival_time
  WHERE NOT EXISTS (
    SELECT 1 FROM bus_order b2
    WHERE b2.arrival_time < b.arrival_time AND p.arrival_time <= b2.arrival_time
  )
)
SELECT b.bus_id, COUNT(a.passenger_id) AS passengers_cnt
FROM Buses b
LEFT JOIN assignments a
  ON b.bus_id = a.bus_id AND a.bus_pos <= b.capacity
GROUP BY b.bus_id
ORDER BY b.bus_id;
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

WITH bus_order AS (
  SELECT *, ROW_NUMBER() OVER (ORDER BY arrival_time) rn
  FROM Buses
),
passenger_order AS (
  SELECT *, ROW_NUMBER() OVER (ORDER BY arrival_time) rn
  FROM Passengers
),
assignments AS (
  SELECT p.passenger_id, b.bus_id, b.arrival_time AS bus_time, b.capacity,
         p.arrival_time AS pass_time,
         ROW_NUMBER() OVER (PARTITION BY b.bus_id ORDER BY p.arrival_time) AS bus_pos
  FROM bus_order b
  JOIN passenger_order p
    ON p.arrival_time <= b.arrival_time
  WHERE NOT EXISTS (
    SELECT 1 FROM bus_order b2
    WHERE b2.arrival_time < b.arrival_time AND p.arrival_time <= b2.arrival_time
  )
)
SELECT b.bus_id, COUNT(a.passenger_id) AS passengers_cnt
FROM Buses b
LEFT JOIN assignments a
  ON b.bus_id = a.bus_id AND a.bus_pos <= b.capacity
GROUP BY b.bus_id
ORDER BY b.bus_id;
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

WITH bus_order AS (
  SELECT *, ROW_NUMBER() OVER (ORDER BY arrival_time) rn
  FROM Buses
),
passenger_order AS (
  SELECT *, ROW_NUMBER() OVER (ORDER BY arrival_time) rn
  FROM Passengers
),
assignments AS (
  SELECT p.passenger_id, b.bus_id, b.arrival_time AS bus_time, b.capacity,
         p.arrival_time AS pass_time,
         ROW_NUMBER() OVER (PARTITION BY b.bus_id ORDER BY p.arrival_time) AS bus_pos
  FROM bus_order b
  JOIN passenger_order p
    ON p.arrival_time <= b.arrival_time
  WHERE NOT EXISTS (
    SELECT 1 FROM bus_order b2
    WHERE b2.arrival_time < b.arrival_time AND p.arrival_time <= b2.arrival_time
  )
)
SELECT b.bus_id, COUNT(a.passenger_id) AS passengers_cnt
FROM Buses b
LEFT JOIN assignments a
  ON b.bus_id = a.bus_id AND a.bus_pos <= b.capacity
GROUP BY b.bus_id
ORDER BY b.bus_id;

Complexity

  • ⏰ Time complexity: O(N log N + M log M) (N = buses, M = passengers)
  • 🧺 Space complexity: O(N + M)