基于时间线重叠拆分区间并获取最大得分的SQL方案

给定两条时间线A和B，每条时间线由非重叠的区间组成，每个区间关联一个得分，需完成以下处理：

• 拆分所有时间段：重叠区间取A、B中的最大得分及对应起止时间
• 非重叠区间保留原起止时间与对应得分
• 区间端点重合时，判定为重叠（包含端点）

可视化说明 #

以下示例展示了时间线A、B及目标结果时间线R的区间与得分分布：

0        1         2         3         4         5
    12345678901234567890123456789012345678901234567890
A =     |---------|        |--|    |--------| |--|
B = |--------|--------| |--------|    |--|        |--|

R = |---|----|----|---| |--|--|--| |--|--|--| |--||--|

Scores per interval:
A =     |---10----|        |20|    |---30---| |40|
B = |---6----|---12---| |---17---|    |33|        |50|

R = |6--|10--|12--|12-| |17|20|17| |30|33|30| |40||50|

示例代码 #

DROP TABLE IF EXISTS #TABLE_A
CREATE TABLE #TABLE_A (
timeline varchar(1),
time_start int,
time_end int,
score int
)

DROP TABLE IF EXISTS #TABLE_B
CREATE TABLE #TABLE_B (
timeline varchar(1),
time_start int,
time_end int,
score int
)

DROP TABLE IF EXISTS #TABLE_R
CREATE TABLE #TABLE_R (
time_start int,
time_end int,
score int
)

INSERT INTO #TABLE_A 
VALUES 
('A', 5, 15, 10)
,('A', 24, 27, 20)
,('A', 32, 41, 30)
,('A', 43, 46, 40)

INSERT INTO #TABLE_B 
VALUES 
('B', 1, 10, 6)
,('B', 10, 19, 12)
,('B', 21, 30, 17)
,('B', 35, 38, 33)
,('B', 47, 50, 50)

INSERT INTO #TABLE_R 
VALUES 
(1, 5, 6)
,(5, 10, 10)
,(10, 15, 12)
,(15, 19, 12)
,(21, 24, 17)
,(24, 27, 20)
,(27, 30, 17)
,(32, 35, 30)
,(35, 38, 33)
,(38, 41, 30)
,(43, 46, 40)
,(47, 50, 50)

尝试思路及遇到的问题 #

我之前尝试枚举所有重叠场景来确定区间起止与得分，但非重叠区间的选取难度较大，需要大量联合操作，因此寻求更简洁的区间拆分方案。

最优解决方案 #

找到一种无需生成完整值域的方案，尤其适用于时间戳场景及大数据集（可避免递归限制问题）。该方案先提取所有关键时间点（两个时间线的所有区间起止点），排序后配对成连续区间，再为每个区间选取最大得分：

WITH points AS (
    SELECT time_start AS 'point' FROM #TABLE_A
    UNION
    SELECT time_end FROM #TABLE_A
    UNION
    SELECT time_start FROM #TABLE_B
    UNION
    SELECT time_end FROM #TABLE_B
),

points_row as (
    SELECT 
    point
    ,ROW_NUMBER() OVER(ORDER BY point) AS row_num
    FROM points
),

time_periods AS (
    SELECT
    s.point AS 'time_start'
    ,e.point AS 'time_end'
    FROM points_row s
    LEFT JOIN points_row e on s.row_num + 1 = e.row_num
)

SELECT * FROM (
    SELECT 
    tp.time_start
    ,tp.time_end
    ,CASE 
    WHEN A.score IS NULL AND B.score IS NULL THEN NULL
    WHEN A.score IS NULL THEN B.score
    WHEN B.score IS NULL THEN A.score
    WHEN A.score > B.score THEN A.score else B.score
    END AS 'score'
    FROM time_periods tp
    LEFT JOIN #TABLE_A A ON A.time_start <= tp.time_start AND A.time_end >= tp.time_end
    LEFT JOIN #TABLE_B B ON B.time_start <= tp.time_start AND B.time_end >= tp.time_end
) a
WHERE score IS NOT NULL

内容的提问来源于stack exchange，提问作者Atoqaz