使用SQLite筛选无重叠时间区间的替代方案咨询

需求说明 #

• 表test包含timeid、start、end字段，timeid与start组合唯一
• 需筛选出同一timeid下无重叠的区间集合，且该集合是最大子集：无法再加入任何未选中的区间而不破坏无重叠规则

示例数据 #

CREATE TABLE "test" (
    "timeid" INTEGER,
    "start"  INTEGER,
    "end"    INTEGER
);
INSERT INTO test VALUES(1, 0, 10);
INSERT INTO test VALUES(1, 2, 13);
INSERT INTO test VALUES(1, 3, 15);
INSERT INTO test VALUES(1, 11, 21);
INSERT INTO test VALUES(1, 15, 30);
INSERT INTO test VALUES(2, 0, 10);
INSERT INTO test VALUES(2, 2, 13);
INSERT INTO test VALUES(2, 11, 21);
INSERT INTO test VALUES(2, 15, 30);

原方案问题 #

原尝试的递归CTE因包含聚合操作触发SQLite报错「递归聚合查询不支持」，代码如下：

with recursive nol(id, start, end) AS (
  select test.timeid, test.start, test.end from test inner join 
 ( select timeid as ttid, min(start) as ttstart from test group by id)  as tt on
 tt.ttid = test.timeid and tt.ttstart = test.start
    union all 
    select test.timeid , test.start, test.end from test  inner join nol 
    on test.timeid = nol.id and test.start > nol.end    
    GROUP By test.timeid
    Having min(test.start)
)
select * from nol 

替代方案：贪心策略递归CTE #

采用经典的贪心算法：同一timeid下优先选择结束最早的区间，再依次选择后续不重叠的区间，确保得到的子集是数量最多的最大子集。

实现代码 #

WITH RECURSIVE sorted_intervals AS (
    -- 按timeid分组，每个组内按end升序排列并编号
    SELECT 
        timeid,
        start,
        end,
        ROW_NUMBER() OVER (PARTITION BY timeid ORDER BY end) AS rn
    FROM test
),
max_subset AS (
    -- 初始集：每个timeid下结束最早的区间（rn=1）
    SELECT timeid, start, end, rn
    FROM sorted_intervals
    WHERE rn = 1
    UNION ALL
    -- 递归选择下一个不重叠的区间：同timeid下start大于上一个区间end，且是该条件下结束最早的（rn最小）
    SELECT si.timeid, si.start, si.end, si.rn
    FROM sorted_intervals si
    JOIN max_subset ms ON si.timeid = ms.timeid
    WHERE si.start > ms.end
      AND si.rn = (
          SELECT MIN(rn) 
          FROM sorted_intervals si2 
          WHERE si2.timeid = ms.timeid 
            AND si2.start > ms.end
      )
)
SELECT timeid, start, end
FROM max_subset
ORDER BY timeid, start;

代码逻辑 #

1. sorted_intervals：对每个timeid下的区间按结束时间升序编号，确保结束最早的区间排在最前
2. 递归初始集：选取每个timeid的第一个区间（结束最早）
3. 递归迭代：对每个已选中的区间，找到同timeid下所有不重叠区间中结束最早的那个，加入结果集
4. 最终按timeid和start排序输出

另一种方案：动态规划回溯法 #

如果需要严格保证是元素数量最多的最大子集（贪心策略已满足，但动态规划可验证），可采用动态规划+回溯的方式：

实现代码 #

WITH sorted AS (
    SELECT 
        timeid,
        start,
        end,
        ROW_NUMBER() OVER (PARTITION BY timeid ORDER BY end) AS rn
    FROM test
),
prev_selected AS (
    SELECT 
        s.*,
        -- 找到当前区间之前，最后一个end <= 当前start的区间编号
        MAX(CASE WHEN s2.end <= s.start THEN s2.rn ELSE 0 END) AS last_valid_rn
    FROM sorted s
    LEFT JOIN sorted s2 ON s.timeid = s2.timeid AND s2.rn < s.rn
    GROUP BY s.timeid, s.rn, s.start, s.end
),
dp AS (
    SELECT 
        *,
        -- 计算选中当前区间时的最大子集数量
        COALESCE((SELECT dp_count FROM dp WHERE timeid = p.timeid AND rn = p.last_valid_rn), 0) + 1 AS dp_count,
        -- 标记当前区间是否被选中
        CASE 
            WHEN COALESCE((SELECT dp_count FROM dp WHERE timeid = p.timeid AND rn = p.last_valid_rn), 0) + 1 > COALESCE((SELECT dp_count FROM dp WHERE timeid = p.timeid AND rn = p.rn -1), 0)
            THEN 1
            ELSE 0
        END AS selected
    FROM prev_selected p
    ORDER BY timeid, rn
),
selected_intervals AS (
    -- 从最后一个区间开始回溯选中的区间
    SELECT timeid, rn, start, end
    FROM dp
    WHERE rn = (SELECT MAX(rn) FROM dp WHERE timeid = dp.timeid)
    UNION ALL
    SELECT dp.timeid, dp.rn, dp.start, dp.end
    FROM dp
    JOIN selected_intervals si ON dp.timeid = si.timeid AND dp.rn = (SELECT last_valid_rn FROM dp WHERE timeid = si.timeid AND rn = si.rn)
    WHERE dp.selected = 1
)
SELECT timeid, start, end
FROM selected_intervals
ORDER BY timeid, start;

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