Problem

Table: Buses

+--------------+------+
| Column Name  | Type |
+--------------+------+
| bus_id       | int  |
| arrival_time | int  |
+--------------+------+
bus_id is the column with unique values for this table.
Each row of this table contains information about the arrival time of a bus at the LeetCode station.
No two buses will arrive at the same time.

Table: Passengers

+--------------+------+
| Column Name  | Type |
+--------------+------+
| passenger_id | int  |
| arrival_time | int  |
+--------------+------+
passenger_id is the column with unique values for this table.
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 time tbus and a passenger arrived at time tpassenger where tpassenger <= tbus and the passenger did not catch any bus, the passenger will use that 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

Input: 
Buses table:
+--------+--------------+
| bus_id | arrival_time |
+--------+--------------+
| 1      | 2            |
| 2      | 4            |
| 3      | 7            |
+--------+--------------+
Passengers table:
+--------------+--------------+
| passenger_id | arrival_time |
+--------------+--------------+
| 11           | 1            |
| 12           | 5            |
| 13           | 6            |
| 14           | 7            |
+--------------+--------------+
Output: 
+--------+----------------+
| bus_id | passengers_cnt |
+--------+----------------+
| 1      | 1              |
| 2      | 0              |
| 3      | 3              |
+--------+----------------+
Explanation: 
- Passenger 11 arrives at time 1.
- Bus 1 arrives at time 2 and collects passenger 11.
- Bus 2 arrives at time 4 and does not collect any passengers.
- 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, 13, and 14.

Solution

Method 1 - Window Functions and Assignment

We assign each passenger to the earliest bus they can catch, 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

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, p.arrival_time AS pass_time
  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
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

WITH bus_order AS (
  SELECT bus_id, arrival_time, ROW_NUMBER() OVER (ORDER BY arrival_time) rn
  FROM Buses
),
passenger_order AS (
  SELECT passenger_id, arrival_time, 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, p.arrival_time AS pass_time
  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
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

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, p.arrival_time AS pass_time
  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
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)