主页 / dba / 问题 / 321392
Accepted
Rishav Ghosh
Asked: 2022-12-24 11:23:31 +0800 CST

如果有容量，我该如何编写查询将乘客安排在公共汽车上？

  • 772

公共汽车和乘客到达车站。如果公共汽车在某个时间到达车站tbus 并且乘客在某个时间到达tpassenger where tpassenger <= tbus，那么乘客将尝试使用第一辆可用的未超过载客量的公共汽车。

如果在公交车到达车站的那一刻等待的乘客多于其容量capacity，则只有capacity乘客会乘坐公交车。

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

输入：

巴士表：

bus_id 到达时间 容量
1个 2个 1个
2个 4个 10
3个 7 2个

乘客表：

passenger_id 到达时间
11 1个
12 1个
13 5个
14 6个
15 7

输出：

bus_id 容量 b_arrival 点 passenger_id p_arrival
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)
sql-server

1 个回答

  1. Best Answer

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

    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
    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 写入具有适当索引的临时表。

    • 4

相关问题