根据MySQL中的公交车容量将乘客分配到公交车上

Question

问题：公交车和乘客到达车站。如果公共汽车在时间tbus到达车站，而乘客在时间tpassenger到达车站，其中tpassenger<= tbus，则乘客将尝试使用容量尚未超过的第一辆可用公共汽车。如果公交车到达车站时，等待的乘客人数超过其容量capacity，则只有capacity的乘客会使用公交车。

编写一个SQL查询来报告每辆公交车上出现的用户(如果两名乘客同时到达，则应优先考虑passenger_id值较小的乘客(。查询结果格式如下例所示(架构和表描述出现在本文末尾(。

示例

输入：

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            |
+--------------+--------------+

输出：

+--------+----------+-----------+------+--------------+-----------+
| 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         |
+--------+----------+-----------+------+--------------+-----------+

解释：

• 乘客11在时间1到达
• 乘客12在时间1到达。
  • 公交车1在时间2到达，由于有一个空座位，因此将乘客11接走
  • 公共汽车2在时间4到达并且由于它有十个空座位而收集乘客12
• 乘客13在时间5到达
• 乘客14在时间6到达
• 乘客15在时间7到达。
  • 3号巴士在时间7到达，由于有两个空座位，因此将乘客13和14接走

---

尝试

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;

给出

+--------+-----------+----------+------+
| 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 |
+--------+-----------+----------+------+

作为其结果集，而

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;

给出

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

作为其结果集。但我不确定如何有效地关联CTE结果集(或者这是否是处理事情的最佳方式(，特别是考虑到有效处理capacity带来的复杂性。

问题：关于如何解决这类问题(最好不使用变量(，有什么想法吗？作为参考，我使用的是MySQL8.0.26。

---

模式和表格说明

架构：

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);

表格描述：

Buses:

+--------------+------+
| Column Name  | Type |
+--------------+------+
| bus_id       | int  |
| arrival_time | int  |
| capacity     | int  |
+--------------+------+

• bus_id是该表的主键列
• 该表的每一行都包含关于公交车到达车站的时间及其capacity(即其空座位数量(的信息
• 不会有两条总线同时到达，capacity将是一个正整数

Passengers:

+--------------+------+
| Column Name  | Type |
+--------------+------+
| passenger_id | int  |
| arrival_time | int  |
+--------------+------+

• passenger_id是该表的主键列
• 该表的每一行都包含乘客到达车站的时间信息

Answer 1

使用递归cte和几个连续的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