⓷妙！探索12306车内换座的最优分配法

WITH available AS (
    SELECT *
    FROM train_seats
    WHERE train_id = 'G322' 
      AND status = 'AVAILABLE'
      -- 如果对旅程路段有要求就写在这里
      -- AND segment BETWEEN 开始 AND 结束
),
s AS ( 
    -- 这个子查询找出从每个段出发能够坐得最远的那些座位, 假设路段segment都是连续的正整数
    SELECT *
    FROM (
        SELECT t.*
             , ROW_NUMBER() OVER (PARTITION BY first_segment ORDER BY cnt DESC) rn
             -- 每个段只需留下能坐得最长的一个座位
        FROM available
        MATCH_RECOGNIZE (
            -- 识别出每张票最多能连续坐几段
            PARTITION BY car_no, seat_no
            ORDER BY segment
            MEASURES
MIN(segment) AS first_segment,
                MAX(segment) AS last_segment,
                COUNT(*) AS cnt
            ONE ROW PER MATCH
            PATTERN (strt a*)
            DEFINE a AS segment = PREV(segment) + 1
        ) t
    )
WHERE rn = 1
    -- 这个筛选过后数据已经很少了，每个路段最多留下一行数据，递归的工作量很少
),
t(last_segment, path, rn) AS (
    -- 执行递归SQL，利用上述结果拼出完整的行程
    SELECT last_segment,
           '段'|| first_segment || ':' || car_no || '车:' || seat_no AS path,
           1 AS rn
    FROM s
    WHERE first_segment = 1
    -- 假设旅程开始段从1开始，也可以修改
    UNION ALL
    SELECT s.last_segment,
           t.path || '->'|| '段'|| first_segment || ':'|| s.car_no || '车:'|| s.seat_no,
           ROW_NUMBER() OVER (ORDER BY s.last_segment DESC) rn
           -- 那些拼上去的座位按终点路段排序找出最远的
    FROM t, s
    WHERE t.rn = 1
      -- 只需留下能够走得最远的那一个座位
      AND s.first_segment <= t.last_segment + 1 
      AND s.last_segment > t.last_segment
)
SELECT path
FROM t
WHERE rn = 1
  AND last_segment = 5
  -- 终点路段为5，可以根据需求修改
;

WITH available AS (
    SELECT train_seats.*,
           segment - ROW_NUMBER() OVER (PARTITION BY car_no, seat_no ORDER BY segment) AS grp_id
           -- 连续序号的差值作为分组依据
    FROM train_seats
    WHERE train_id = 'G322' 
      AND status = 'AVAILABLE'
      -- 如果对旅程路段有要求就写在这里
      -- AND segment BETWEEN 开始 AND 结束
),
s AS (
    -- 这个子查询找出从每个段出发能够坐得最远的那些座位, 假设路段segment都是连续的正整数
    SELECT * FROM (
        SELECT car_no, seat_no,
               MIN(segment) AS first_segment,
               MAX(segment) AS last_segment,
               COUNT(*) AS cnt,
               ROW_NUMBER() OVER ( PARTITION BY MIN(segment) ORDER BY COUNT(*) DESC) rn
               -- 每个段只需留下能坐得最长的一个座位
        FROM available
        GROUP BY car_no, seat_no, grp_id
    )
WHERE rn = 1
    -- 这个筛选过后数据已经很少了，每个路段最多留下一行数据，递归的工作量很少
)
SELECT* FROM (
    SELECT SYS_CONNECT_BY_PATH ('段'|| first_segment || ':'|| car_no || '车:'|| seat_no, '->') AS path,
           LEVEL AS change_count
    FROM s
    WHERE last_segment = 5
    -- 终点路段为5，可以根据需求修改
    START WITH first_segment = 1
    CONNECT BY first_segment <= PRIOR last_segment + 1 AND last_segment > PRIOR last_segment
    ORDER BY LEVEL
)
WHERE ROWNUM = 1;

5

结语