Assigning passengers to buses based on bus capacity in MySQL

user_5209533 0
Viewed 521

Problem: Buses and passengers arrive at a station. If a bus arrives at the station at a time tbus and a passenger arrives at a time tpassenger where tpassenger <= tbus, then the passenger will attempt to use the first available bus whose capacity has not been exceeded. 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 SQL query to report the users that appear on each bus (if two passengers arrive at the same time, then the passenger with the smaller passenger_id value should be given priority). The query result format is in the following example (schema and table descriptions appear at the end of this post).

Example

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 | capacity | b_arrival | spot | passenger_id | p_arrival |
+--------+----------+-----------+------+--------------+-----------+
|      1 |        1 |         2 |    1 | 11           | 1         |
|      2 |       10 |         4 |    1 | 12           | 1         |
|      2 |       10 |         4 |    2 | NULL         | NULL      |
|      2 |       10 |         4 |    3 | NULL         | NULL      |
|      2 |       10 |         4 |    4 | NULL         | NULL      |
|      2 |       10 |         4 |    5 | NULL         | NULL      |
|      2 |       10 |         4 |    6 | NULL         | NULL      |
|      2 |       10 |         4 |    7 | NULL         | NULL      |
|      2 |       10 |         4 |    8 | NULL         | NULL      |
|      2 |       10 |         4 |    9 | NULL         | NULL      |
|      2 |       10 |         4 |   10 | NULL         | NULL      |
|      3 |        2 |         7 |    1 | 13           | 5         |
|      3 |        2 |         7 |    2 | 14           | 6         |
+--------+----------+-----------+------+--------------+-----------+

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 13 arrives at time 5.
  • Passenger 14 arrives at time 6.
  • Passenger 15 arrives at time 7.
    • Bus 3 arrives at time 7 and collects passengers 13 and 14 as it has two empty seats.

Attempt

The CTE

WITH RECURSIVE bus_spots AS (
  SELECT B.bus_id, B.arrival_time AS b_arrival, B.capacity, 1 AS spot FROM Buses B
  UNION ALL
  SELECT BS.bus_id, BS.b_arrival, BS.capacity, BS.spot + 1 FROM bus_spots BS WHERE BS.spot < BS.capacity
) SELECT * FROM bus_spots ORDER BY bus_id, spot;

gives

+--------+-----------+----------+------+
| bus_id | b_arrival | capacity | spot |
+--------+-----------+----------+------+
|      1 |         2 |        1 |    1 |
|      2 |         4 |       10 |    1 |
|      2 |         4 |       10 |    2 |
|      2 |         4 |       10 |    3 |
|      2 |         4 |       10 |    4 |
|      2 |         4 |       10 |    5 |
|      2 |         4 |       10 |    6 |
|      2 |         4 |       10 |    7 |
|      2 |         4 |       10 |    8 |
|      2 |         4 |       10 |    9 |
|      2 |         4 |       10 |   10 |
|      3 |         7 |        2 |    1 |
|      3 |         7 |        2 |    2 |
+--------+-----------+----------+------+

as its result set while

WITH bus_queue AS (
  SELECT
    P.passenger_id,
    P.arrival_time AS p_arrival,
    ROW_NUMBER() OVER(ORDER BY P.arrival_time, P.passenger_id) AS queue_pos
  FROM Passengers P
) SELECT * FROM bus_queue ORDER BY p_arrival, passenger_id;

gives

+--------------+-----------+-----------+
| passenger_id | p_arrival | queue_pos |
+--------------+-----------+-----------+
|           11 |         1 |         1 |
|           12 |         1 |         2 |
|           13 |         5 |         3 |
|           14 |         6 |         4 |
|           15 |         7 |         5 |
+--------------+-----------+-----------+

as its result set. But I'm not sure how to effectively relate the CTE result sets (or if this is even the best way of going about things), especially given the complications introduced by handling capacity effectively.

Question: Any ideas on how to work out a solution for this kind of problem (preferably without using variables)? For reference, I'm using MySQL 8.0.26.

Schema and Table Descriptions

Schema:

DROP TABLE IF EXISTS Buses;

CREATE TABLE IF NOT EXISTS
  Buses (bus_id int, arrival_time int, capacity int);

INSERT INTO
  Buses (bus_id, arrival_time, capacity)
VALUES
  (1, 2, 1),
  (2, 4, 10),
  (3, 7, 2);


DROP TABLE IF EXISTS Passengers;

CREATE TABLE IF NOT EXISTS
  Passengers (passenger_id int, arrival_time int);

INSERT INTO
  Passengers (passenger_id, arrival_time)
VALUES
  (11, 1),
  (12, 1),
  (13, 5),
  (14, 6),
  (15, 7);

Table descriptions:

Buses:

+--------------+------+
| Column Name  | Type |
+--------------+------+
| bus_id       | int  |
| arrival_time | int  |
| capacity     | int  |
+--------------+------+
  • bus_id is the primary key column for this table.
  • Each row of this table contains information about the arrival time of a bus at the station and its capacity (i.e., the number of empty seats it has).
  • There will be no two buses that arrive at the same time and capacity will be a positive integer.

Passengers:

+--------------+------+
| Column Name  | Type |
+--------------+------+
| passenger_id | int  |
| arrival_time | int  |
+--------------+------+
  • passenger_id is the primary key column for this table.
  • Each row of this table contains information about the arrival time of a passenger at the station.
common-table-expression mysql sql
1 Answers

Using a recursive cte and several successive ctes:

with recursive cte(id, a, c, s) as (
  select b.*, 1 from buses b
  union all
  select c.id, c.a, c.c, c.s + 1 from cte c where c.s+1 <= c.c 
),
_passengers as (
  select row_number() over (order by p.passenger_id) n, p.* from passengers p
),
gps(bid, n, a, pid) as (
  select b.bus_id, p.n, p.arrival_time, p.passenger_id from buses b 
  join _passengers p on p.arrival_time <= b.arrival_time and not exists 
     (select 1 from buses b1 where b1.arrival_time < b.arrival_time and p.arrival_time <= b1.arrival_time)
),
slts(v, n, a, pid) as (
  select case when 
     (select sum(g.bid = g1.bid and g1.n <= g.n) from gps g1) <= (select sum(c.id = g.bid) from cte c) 
     then g.bid else null end, g.n, g.a, g.pid from gps g
),
dists as (
  select case when s.v is not null 
     then s.v 
     else (select min(b.bus_id) from buses b where b.arrival_time >= s.a and
             (select sum(s2.v is null and s2.n <= s.n) from slts s2) < 
             (select sum(c3.id = b.bus_id) from cte c3)) end v, 
     s.a, s.pid from slts s
)       
select c.id bus_id, c.c capacity, c.a arrival_time, c.s spot, p.pid passenger_id, p.a arrival from cte c 
left join (select (select sum(d.v = d1.v and d1.a < d.a) from dists d1) + 1 r, 
           d.* from dists d where d.v is not null) p 
on c.id = p.v and c.s = p.r
order by c.a, c.s
user_73267380
Related