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:

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

[{"language":"MySQL","code":"WITH bus_order AS (\n  SELECT *, ROW_NUMBER() OVER (ORDER BY arrival_time) AS rn\n  FROM Buses\n),\npassenger_order AS (\n  SELECT *, ROW_NUMBER() OVER (ORDER BY arrival_time) AS rn\n  FROM Passengers\n),\nassignments AS (\n  SELECT p.passenger_id, b.bus_id, b.arrival_time AS bus_time, b.capacity,\n         p.arrival_time AS pass_time,\n         ROW_NUMBER() OVER (PARTITION BY b.bus_id ORDER BY p.arrival_time) AS bus_pos\n  FROM bus_order b\n  JOIN passenger_order p\n    ON p.arrival_time <= b.arrival_time\n  WHERE NOT EXISTS (\n    SELECT 1 FROM bus_order b2\n    WHERE b2.arrival_time < b.arrival_time AND p.arrival_time <= b2.arrival_time\n  )\n)\nSELECT b.bus_id, COUNT(a.passenger_id) AS passengers_cnt\nFROM Buses b\nLEFT JOIN assignments a\n  ON b.bus_id = a.bus_id AND a.bus_pos <= b.capacity\nGROUP BY b.bus_id\nORDER BY b.bus_id;","lang":"sql"},{"language":"Oracle","code":"WITH bus_order AS (\n  SELECT *, ROW_NUMBER() OVER (ORDER BY arrival_time) rn\n  FROM Buses\n),\npassenger_order AS (\n  SELECT *, ROW_NUMBER() OVER (ORDER BY arrival_time) rn\n  FROM Passengers\n),\nassignments AS (\n  SELECT p.passenger_id, b.bus_id, b.arrival_time AS bus_time, b.capacity,\n         p.arrival_time AS pass_time,\n         ROW_NUMBER() OVER (PARTITION BY b.bus_id ORDER BY p.arrival_time) AS bus_pos\n  FROM bus_order b\n  JOIN passenger_order p\n    ON p.arrival_time <= b.arrival_time\n  WHERE NOT EXISTS (\n    SELECT 1 FROM bus_order b2\n    WHERE b2.arrival_time < b.arrival_time AND p.arrival_time <= b2.arrival_time\n  )\n)\nSELECT b.bus_id, COUNT(a.passenger_id) AS passengers_cnt\nFROM Buses b\nLEFT JOIN assignments a\n  ON b.bus_id = a.bus_id AND a.bus_pos <= b.capacity\nGROUP BY b.bus_id\nORDER BY b.bus_id;","lang":"sql"},{"language":"PostgreSQL","code":"WITH bus_order AS (\n  SELECT *, ROW_NUMBER() OVER (ORDER BY arrival_time) rn\n  FROM Buses\n),\npassenger_order AS (\n  SELECT *, ROW_NUMBER() OVER (ORDER BY arrival_time) rn\n  FROM Passengers\n),\nassignments AS (\n  SELECT p.passenger_id, b.bus_id, b.arrival_time AS bus_time, b.capacity,\n         p.arrival_time AS pass_time,\n         ROW_NUMBER() OVER (PARTITION BY b.bus_

Related Tags