如何判断给定pair列表中存在无间隙覆盖指定range的chain？

定义与示例 #

给定一个Range，比如：

range : 1 4

存在3组可无间隙覆盖该Range的Pair列表，我们称之为Chain：

chain1: 1 2, 2 3, 3 4
chain2: 1 2, 2 4
chain3: 1 3, 3 4

以下Pair列表无法覆盖该Range，因此不属于Chain：

1 2       <= 缺失 2 3, 3 4 或 2 4
1 3       <= 缺失 3 4
1 2, 3 4  <= 缺失 2 3
1 2, 2 3  <= 缺失 3 4
2 3, 3 4  <= 缺失 1 2

技术问题 #

给定一组随机Pair列表和一个指定Range，如何判断其中是否存在可构成Chain的Pair组合？

已知条件 #

• Pair不重复，均为（低值，高值）形式
• Pair无重叠（不会出现[1 3, 2 4]这类输入）
• 已预先过滤出Range内的Pair，无需考虑超出Range的Pair（如4 6、7 9、0 1）

补充说明 #

以下形式也属于有效Chain：

chain: 1 2, 1 3, 3 4
chain: 1 2, 1 3, 1 4
chain: 1 2, 2 4, 3 4

即Pair可包含其他Pair（一个Pair可覆盖另一个Pair的Range），这种情况会打破常规的排序遍历思路。

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