如何生成无重叠的多组区间笛卡尔积以缩减计算规模？
2026-5-1
缩减区间笛卡尔积规模：过滤无重叠区间组合
问题背景
我们手头有一个包含多组时间区间的字典：
intervals = {'561801/03/08': [[1081, 1156], [1141, 1216], [1201, 1276], [1741, 1816], [1801, 1876], [1861, 1936], [1921, 1996], [1981, 2056], [2041, 2116]], '563301/03/08': [[1170, 1250], [1230, 1310], [1770, 1850], [1830, 1910], [1890, 1970], [1950, 2030], [2010, 2090], [2070, 2150], [2130, 2210]], '688002/03/08': [[1790, 1850], [1850, 1910], [1910, 1970], [1970, 2030], [2090, 2150], [2150, 2210], [2210, 2270], [2270, 2330], [2330, 2390], [2390, 2450], [2450, 2510], [2510, 2570], [2570, 2630], [2630, 2690], [2690, 2750]], '690102/03/08': [[1900, 1960], [1960, 2020], [2020, 2080], [2080, 2140], [2200, 2260], [2260, 2320], [2320, 2380], [2380, 2440], [2440, 2500], [2500, 2560], [2560, 2620], [2620, 2680], [2680, 2740]], '559402/03/08': [[2015, 2090], [2075, 2150], [2135, 2210], [2195, 2270], [2255, 2330], [2315, 2390], [2375, 2450], [2435, 2510], [2495, 2570], [2555, 2630], [2615, 2690], [2675, 2750]], '561302/03/08': [[2310, 2390], [2370, 2450], [2430, 2510], [2490, 2570], [2550, 2630], [2610, 2690], [2670, 2750]], '572602/03/08': [[2435, 2505], [2495, 2565], [2555, 2625], [2615, 2685], [2675, 2745]], '572502/03/08': [[2560, 2640], [2620, 2700]]}
如果直接用itertools.product(*intervals.values())生成笛卡尔积，总规模会达到9×9×15×13×12×7×5×2=13,267,800，这种先全量生成再过滤的方式效率极低，完全不实用。
核心需求
我们需要过滤掉所有包含两个或多个重叠区间的组合，只保留无重叠的合法组合：
- 合法组合示例：
[1081, 1156], [1170, 1250], [1790, 1850], [1900, 1960], [2015, 2090], [2310, 2390], [2435, 2505], [2560, 2640]（所有区间互不重叠） - 非法组合示例：
[1141, 1216], [1170, 1250], [1790, 1850], [1900, 1960], [2015, 2090], [2310, 2390], [2435, 2505], [2560, 2640]（前两个区间[1141, 1216]与[1170, 1250]重叠，这类无效组合就有15×13×12×7×5×2=163,800个，必须全部排除）
高效解决方案：回溯剪枝法
直接生成全部笛卡尔积再过滤显然不现实，我们可以用回溯+剪枝的思路，每一步只选择当前组中与已选所有区间不重叠的区间，提前排除无效路径，大幅减少计算量：
步骤说明
- 先定义辅助函数判断两个区间是否重叠：对于闭区间
[a1,a2]和[b1,b2]，重叠的条件是not (a2 <= b1 or b2 <= a1)（只要不是完全不重叠，就算重叠） - 把字典中的区间组按固定顺序提取出来（顺序不影响最终结果，但固定顺序方便回溯逻辑）
- 用回溯算法遍历每个组：每一步选择当前组中与已选区间都不重叠的区间，递归进入下一组；当选完所有组时，记录这个合法组合
Python代码实现
def is_overlap(interval1, interval2): # 判断两个闭区间是否重叠 return not (interval1[1] <= interval2[0] or interval2[1] <= interval1[0]) def has_overlap(new_interval, selected_intervals): # 检查新区间是否与已选的任何区间重叠 for interval in selected_intervals: if is_overlap(interval, new_interval): return True return False def backtrack(groups, index, current, result): if index == len(groups): result.append(current.copy()) return # 遍历当前组的所有可能区间 for interval in groups[index]: if not has_overlap(interval, current): current.append(interval) backtrack(groups, index + 1, current, result) current.pop() # 提取所有区间组（按字典键的顺序） interval_groups = list(intervals.values()) valid_combinations = [] # 执行回溯算法 backtrack(interval_groups, 0, [], valid_combinations) print(f"合法组合总数：{len(valid_combinations)}") print("部分合法组合示例：") for combo in valid_combinations[:5]: print(combo)
进阶优化：排序加速
如果先对每个组的区间按起始时间排序，还能进一步优化重叠判断的效率——因为已选区间如果也保持有序，我们只需要遍历到第一个起始时间大于新区间结束时间的位置就可以停止，不用检查全部已选区间：
# 先对每个组的区间按起始时间排序 interval_groups = [sorted(group, key=lambda x: x[0]) for group in intervals.values()] def has_overlap_sorted(new_interval, current): # current是已排序的区间列表，提前终止判断 for interval in current: if interval[0] > new_interval[1]: break # 后面的区间起始时间更大，不可能重叠 if is_overlap(interval, new_interval): return True return False def backtrack_sorted(groups, index, current, result): if index == len(groups): result.append(current.copy()) return for interval in groups[index]: if not has_overlap_sorted(interval, current): # 将新区间插入到合适位置，保持current有序 insert_pos = 0 while insert_pos < len(current) and current[insert_pos][0] < interval[0]: insert_pos += 1 current.insert(insert_pos, interval) backtrack_sorted(groups, index + 1, current, result) current.pop(insert_pos) valid_combinations_sorted = [] backtrack_sorted(interval_groups, 0, [], valid_combinations_sorted)
这种方法避免了生成全部1300多万个组合，而是在每一步就过滤掉无效路径，能极大提升效率，快速得到所有合法的无重叠区间组合。
内容的提问来源于stack exchange，提问作者Francisco Lemos
