Início / dba / Perguntas / 321392
Accepted
Rishav Ghosh
Asked: 2022-12-24 11:23:31 +0800 CST

Como faço uma consulta que coloque passageiros em ônibus se houver lotação?

  • 772

Ônibus e passageiros chegam a uma estação. Se um ônibus chegar à estação em um horário tbus e um passageiro chegar em um horário tpassenger where tpassenger <= tbus, o passageiro tentará usar o primeiro ônibus disponível cuja capacidade não tenha sido excedida.

Se no momento em que o ônibus chegar à estação houver mais passageiros esperando do que sua capacidade capacity, apenas capacitypassageiros usarão o ônibus.

Desejo gerar os usuários que aparecem em cada ônibus (se dois passageiros chegarem ao mesmo tempo, o passageiro com o menor valor de passage_id deve ter prioridade).

Entrada:

Tabela de ônibus:

bus_id tempo de chegada capacidade
1 2 1
2 4 10
3 7 2

Mesa de passageiros:

id_passageiro tempo de chegada
11 1
12 1
13 5
14 6
15 7

Saída:

bus_id capacidade b_chegada ver id_passageiro p_chegada
1 1 2 1 11 1
2 10 4 1 12 1
2 10 4 2 NULO NULO
2 10 4 3 NULO NULO
2 10 4 4 NULO NULO
2 10 4 5 NULO NULO
2 10 4 6 NULO NULO
2 10 4 7 NULO NULO
2 10 4 8 NULO NULO
2 10 4 9 NULO NULO
2 10 4 10 NULO NULO
3 2 7 1 13 5
3 2 7 2 14 6

Explicação:

O passageiro 11 chega no tempo 1.

O passageiro 12 chega no tempo 1.

O ônibus 1 chega no horário 2 e recolhe o passageiro 11, pois tem um assento vazio.

O ônibus 2 chega no horário 4 e recolhe o passageiro 12, pois tem dez lugares vazios.

O passageiro 13 chega no tempo 5.

O passageiro 14 chega no tempo 6.

O passageiro 15 chega no horário 7.

O ônibus 3 chega no horário 7 e recolhe os passageiros 13 e 14, pois tem dois assentos vazios.

DDL:


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 respostas

  1. Best Answer

    Uma maneira de resolver isso é com o seguinte algoritmo:

    1. Enumere os passageiros em ordem de prioridade.
    2. Gere uma linha para cada ponto de barramento e enumere todas as linhas em ordem de prioridade.
    3. Para o primeiro passageiro, encontre o primeiro ponto de ônibus disponível e acompanhe o ponto de ônibus que foi usado.
    4. Para cada passageiro subseqüente, encontre o primeiro ponto de ônibus disponível após o ponto de ônibus que foi usado pelo passageiro anterior.

    Esse algoritmo pode ser implementado usando um CTE recursivo. Por exemplo:

    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;

    Eu obtenho a saída desejada para seus dados de amostra:

    insira a descrição da imagem aqui

    Conforme implementado, essa abordagem provavelmente não funcionará bem em tabelas grandes. Uma maneira de melhorar o desempenho de tabelas maiores seria gravar algumas das CTEs em tabelas temporárias com índices apropriados.

    • 4

relate perguntas