如果有容量，如何编写将乘客安排到公交车上的查询？

Question

公共汽车和乘客到达车站。如果某时间有一辆公共汽车到达车站tbus ，并且某时间有一名乘客到达tpassenger where tpassenger <= tbus，则该乘客将尝试使用第一辆未超出容量的可用公共汽车。

如果公交车到达车站时等待的乘客数量超过了其容量capacity，则只有capacity乘客才会乘坐公交车。

我想输出每辆公交车上出现的用户（如果两个乘客同时到达，则应优先考虑passenger_id值较小的乘客）。

输入：

巴士表：

总线 ID	到达时间	容量
1	2	1
2	4	10
3	7	2

旅客表：

乘客 ID	到达时间
11	1
12	1
13	5
14	6
15	7

输出：

总线 ID	容量	b_到达	点	乘客 ID	p_到达
1	1	2	1	11	1
2	10	4	1	12	1
2	10	4	2	无效的	无效的
2	10	4	3	无效的	无效的
2	10	4	4	无效的	无效的
2	10	4	5	无效的	无效的
2	10	4	6	无效的	无效的
2	10	4	7	无效的	无效的
2	10	4	8	无效的	无效的
2	10	4	9	无效的	无效的
2	10	4	10	无效的	无效的
3	2	7	1	13	5
3	2	7	2	14	6

解释：

乘客 11 在时间 1 到达。

乘客 12 在时间 1 到达。

公共汽车 1 在时间 2 到达并接载乘客 11，因为它有一个空座位。

公共汽车 2 在时间 4 到达并接载乘客 12，因为它有 10 个空座位。

乘客 13 于时间 5 到达。

乘客 14 于时间 6 到达。

乘客 15 于时间 7 到达。

公交车 3 号在时间 7 到达并搭载乘客 13 和 14，因为它有两个空座位。

数据定义语言：

create table buses(id int, arrival_time int, capacity int)
insert into buses values(1,2,1),(2,4,10),(3,7,2)
create table passengers (passenger_id int, arrival_time int)
insert into passengers values(11,1),(12,1),(13,5),(14,6),(15,7)

Answer 1

解决这个问题的一种方法是使用以下算法：

1. 按优先顺序枚举乘客。
2. 为每个公交站点生成一行并按优先级顺序枚举所有行。
3. 对于第一位乘客，找到第一个可用的巴士站点并记录所使用的巴士站点。
4. 对于每个后续乘客，找到前一位乘客乘坐的巴士站点之后的第一个可用巴士站点。

该算法可以使用递归 CTE 来实现。例如：

WITH numbers_table AS (
    SELECT TOP (1000) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) AS Num -- will a bus have more than 1000 seats?
    FROM master..spt_values
),
enumerated_passengers AS (
    SELECT p.passenger_id, p.arrival_time AS p_arrival, ROW_NUMBER() OVER (ORDER BY p.arrival_time, p.passenger_id) p_key
    FROM passengers p
),
enumerated_bus_spots AS (
    SELECT b.id bus_id, b.capacity, b.arrival_time AS b_arrival, nums.num AS Spot, ROW_NUMBER() OVER (ORDER BY b.arrival_time, b.id, nums.num) bs_key
    FROM buses b
    INNER JOIN numbers_table nums ON nums.num <= CAST(b.capacity AS BIGINT)
),
boarded_passengers AS (
    SELECT TOP (1) p.passenger_id, p.p_arrival, p.p_key, bs.bs_key Last_Filled_Bus_Spot
    FROM enumerated_passengers p
    INNER JOIN enumerated_bus_spots bs ON p.p_arrival <= bs.b_arrival
    WHERE p.p_key = 1
    ORDER BY bs.bs_key ASC

    UNION ALL

    SELECT q.passenger_id, q.p_arrival, q.p_key, q.bs_key Last_Filled_Bus_Spot
    FROM
    (
        SELECT p.passenger_id, p.p_arrival, p.p_key, bs.bs_key, ROW_NUMBER() OVER (ORDER BY bs.bs_key) RN_temp
        FROM enumerated_passengers p
        INNER JOIN enumerated_bus_spots bs ON p.p_arrival <= bs.b_arrival
        INNER JOIN boarded_passengers c ON p.p_key = c.p_key + 1
        WHERE bs.bs_key > c.Last_Filled_Bus_Spot
    ) q
    WHERE q.RN_temp = 1
)
SELECT bs.bus_id, bs.capacity, bs.b_arrival, bs.spot, bp.passenger_id, bp.p_arrival
FROM enumerated_bus_spots bs
LEFT OUTER JOIN boarded_passengers bp ON bs.bs_key = bp.Last_Filled_Bus_Spot
ORDER BY bs.b_arrival, bs.bus_id, bs.spot;

我得到了您的示例数据所需的输出：

在实施时，这种方法对于大型表来说不太可能表现良好。提高较大表性能的一种方法是将一些 CTE 写入具有适当索引的临时表。