|
|
我自己写了一个：
普通挑战
完成普通挑战的前 50 名选手即可获得参赛纪念奖品
要求选手用一条 SQL 实现乘客分配车次信息，具体要求：
1. 只能用一条 SQL ，可以使用数据库内置函数，不能使用自定义函数和存储过程
2. 每个乘客最多只能分配一个车次
3. 每列火车分配的乘客数不能超过座位数
4. 不能出现火车有空余座位，但对应起始站和终点站的乘客未分配票
5. 如果没有可分配的车次， train_id 返回空值 ( null )
6. 返回结果按 passenger_id 字符顺序排序
返回的结果集示例如下：
思路：需求是将每行乘客记录分配到一趟列车，也就是说连接两张表。连接条件首先是起点和终点站，这两个列重复的火车记录有多行，而每名乘客最多只能连接到其中的一条，所以需要对每趟车做一个编号限制，使得乘客按照编号只能对应到其中的一行。把列车和乘客分别按照起点和终点站分组，同组的乘客按某种方法排序（不妨就按照乘客id排序）利用row_number()获得一个序号，而分组后的列车也按主键排序，根据每趟列车的容量算出其座位序号的上下限，形成一张拉链表，这样就可以用乘客序号和列车座位序号建立一个对应关系，使得每名乘客最多分配到一趟列车。
with p as (
select passenger.*
,row_number() over(partition by departure_station,arrival_station order by passenger_id) rn ---- 为每组起终点的乘客编一个序号
from passenger)
,tr as (
select t.*
,sum(seat_count) over(partition by departure_station,arrival_station order by train_id) s2 ---- 对每组起终点的列车座位数做滚动累计，这个累计值就是座位序号的上限
from train t
)
select p.passenger_id,p.departure_station,p.arrival_station
,tr.train_id
from p left join tr on p.departure_station =tr.departure_station and p.arrival_station =tr.arrival_station
and p.rn between tr.s2-tr.seat_count+1 and tr.s2 ----- 建立乘客序号和座位序号的对应关系，座位号上限是列车容量的滚动累计值，下限则为该累计值减去当前车的容量
;
进阶挑战
完成普通挑战的选手，可以进一步完成进阶挑战。（注：提交进阶挑战 SQL 前必须先提交普通挑战的 SQL ）
进阶挑战性能排名前8的选手进入决赛成绩评选。
在普通挑战基础上，要求给每个乘客分配具体座位号，每列火车根据座位数有若干个车厢（编号 1~N ），每节车厢有 100 个座位，分 20 排，每排5个座位（ A,B,C,E,F ）,注意：没有编号 D 的座位。
每列火车允许发售 10% 的无座票，无座的乘客 coach_number 为空，seat_number =无座
火车票分配时需要优先分配有座的票，即仅当A地到B地的所有有座票分配完后，才分配无座车票
思路：和前面的分配思路一样，无非就是多了无座票，这些无座票可以看作是容量为10%的额外车次，只需把它们叠加到原来车次记录上，在排序编号时优先级放在所有旧车次记录的后面。叠加的方法可以用和两条记录的小集合做笛卡尔积，或者用union all。
分配完了要计算车厢和座位编号，这只是简单的算术：
将当前乘客序号减去本车次座位序号的下限，得到一个车次内的相对序号；
把这个车次内的相对序号除以车厢大小（100），其商就是车厢号，余数则是车厢内的相对序号；
把这个车厢内的相对序号除以每排座位数（5），其商就是排号，余数则是座位号，可以简单地用SUBSTR映射到ABCEF。
with p as (
select passenger.*
,row_number() over(partition by departure_station,arrival_station order by passenger_id) rn ---- 为每组起终点的乘客编一个序号
from passenger)
,tr as (
select tr1.*
,s2-seat_count as s1 ----- 本车次座位序号的下限，上限是s2
from (select train_id,departure_station,arrival_station,flag
,case when flag=0 then seat_count else trunc(seat_count*0.1) end as seat_count ---- flag=0为原车次记录，flag=1为无座票，容量只有10%
,sum(case when flag=0 then seat_count else trunc(seat_count*0.1) end) over(partition by departure_station,arrival_station order by flag,train_id) as s2 ---- 对每组起终点的列车座位数做滚动累计，这个累计值就是座位序号的上限
from train t
cross join (select 0 flag from dual union all select 1 from dual) ---和两条记录的小集合做笛卡尔积，生成额外的车次记录
) tr1
)
select p.passenger_id,p.departure_station,p.arrival_station
,tr.train_id
,case when tr.flag=0 then ceil((p.rn-tr.s1)/100) end as coach_number ---- 算出车厢号
,case when tr.flag=0 then
-- mod(p.rn-tr.s1-1,100)+1 ---得到1-100的编号
ceil((mod(p.rn-tr.s1-1,100)+1)/5)||SUBSTR('FABCE',mod(mod(p.rn-tr.s1-1,100)+1,5)+1,1)
when tr.flag=1 then ' no seat'
end as seat_number
from p left join tr on p.departure_station =tr.departure_station and p.arrival_station =tr.arrival_station
and p.rn between tr.s1+1 and tr.s2 ----- 建立乘客序号和座位序号的对应关系
;
------------
改进思路：上述写法在ORACLE典型的执行计划就是一个带过滤条件的hash join, 等值比较的部分用hash join的access, 不等值比较则用filter。当起终点重复的车次很多，乘客很多时，这个filter是很耗时间的。如果有一种方法把乘客序号和列车上的座位编号建立一种等值对应关系，那么filter就可以省去了，效率会提高很多，这个就是所谓的拉链表流水化。最直接思路是把每个座位都生成出一行记录，这样就和乘客一一对应了，但是容量1600的车次就会变成1600条记录，这个hash表会很大。因为题目限制了车次容量只有600,800,1200,1600这几种，那么取其最大公约数200就可以把每200个座位划分成一个块，这就保证所有车次都能划分成大小均等的块，而乘客序号只需除以200取整就可以建立起这个映射关系。
把不等值比较条件转化为等值比较的技巧，我在十几年前就见itpub的大神用过，几年前和老虎刘讨论时也用过(见下贴20楼)：
https://www.itpub.net/forum.php?mod=viewthread&tid=120140
普通挑战:
with p as (
select passenger.*
,row_number() over(partition by departure_station,arrival_station order by passenger_id) rn ---- 为每组起终点的乘客编一个序号
from passenger)
,tr as (
select tr1.*
,s2-chunk_count+lvl as chunk_id ---- 把每趟车复制成多行，每个分块一行，并进行编号
from (select t.*
,sum(seat_count/200) over(partition by departure_station,arrival_station order by train_id) s2 ---- 把座位数按200分块，然后做滚动累计
,seat_count/200 as chunk_count ----- 计算当前车次要分成多少块
from train t
) tr1
,lateral(select level lvl from dual connect by level<=chunk_count) ---- lateral view会把每一行数据复制成多行
)
select p.passenger_id,p.departure_station,p.arrival_station
,tr.train_id
from p left join tr on p.departure_station =tr.departure_station and p.arrival_station =tr.arrival_station
and ceil(p.rn/200) = tr.chunk_id ----- 建立乘客序号和座位序号的映射关系，只需将乘客号除以200并座取整
;
进阶挑战：和前面类似，但是因为新加入的无座车次记录容量只有10%，分块时也只能按20个座位一个块来分，这样HASH表会膨胀不少，但从效率而言还是值得的。
with p as (
select passenger.*
,row_number() over(partition by departure_station,arrival_station order by passenger_id) rn ---- 为每组起终点的乘客编一个序号
from passenger)
,tr as (
select tr1.*
,s2-chunk_count+lvl as chunk_id ---- 把每趟车复制成多行，每个分块一行，并进行编号
,s2*20-chunk_count*20 as s1 ----- 本车次座位序号的下限，上限是s2
from (select train_id,departure_station,arrival_station,flag
,case when flag=0 then seat_count/20 else trunc(seat_count*0.1/20) end as chunk_count ---- flag=0为原车次记录，flag=1为无座票，容量只有10%, 这样排序时原车优先于无座
,sum(case when flag=0 then seat_count/20 else trunc(seat_count*0.1/20) end) over(partition by departure_station,arrival_station order by flag,train_id) as s2 ---- 把座位数按20分块，然后做滚动累计
from train t
cross join (select 0 flag from dual union all select 1 from dual) ---和两条记录的小集合做笛卡尔积，生成额外的车次记录
) tr1
,lateral(select level lvl from dual connect by level<=chunk_count) ---- lateral view会把每一行数据复制成多行
)
select p.passenger_id,p.departure_station,p.arrival_station
,tr.train_id
,case when tr.flag=0 then ceil((p.rn-tr.s1)/100) end as coach_number ---- 算出车厢号
,case when tr.flag=0 then
-- mod(p.rn-tr.s1-1,100)+1 ---得到1-100的编号
ceil((mod(p.rn-tr.s1-1,100)+1)/5)||SUBSTR('FABCE',mod(mod(p.rn-tr.s1-1,100)+1,5)+1,1)
when tr.flag=1 then ' no seat'
end as seat_number
from p left join tr on p.departure_station =tr.departure_station and p.arrival_station =tr.arrival_station
and ceil(p.rn/20) = tr.chunk_id ----- 建立乘客序号和座位序号的映射关系，只需将乘客号除以20并座取整
;
|
|
楼主: 〇〇
IP卡
狗仔卡
发表于 2024-12-17 22:52
显身卡
楼主