3

我有一个大约 5000 个整数范围的列表（例如 30-50、45-100 等），我需要将它们放入“排序顺序”中。此顺序需要基于哪些列表项是其他项的范围子集。例如 10-12 将是 2-14 的范围子集。如果 list(1).low_value >= list(2).low_value 并且 list(1).upper_value <= list(2).upper_value 那么 list(1) 是 list(2) 的子集。更复杂的是，一些列表项将是许多列表项的子集。

我最终需要创建一个有序列表，以便较低索引处的列表项始终是列表中任何项的子集或不相关（例如范围 1-2 和 3-4）。

谢谢，马克

4

1 回答 1

1

我的第一反应是，这听起来像是一种拓扑排序，其中范围被视为图中的节点，如果 A 是 B 的子范围，则认为从范围 A 到范围 B 存在一条边。

我假设您的意思是输出列表的条件是，如果 A 出现在 B 之前，则 B 不是 A 的严格子集（但是如果 A = B，A 和 B 不相交，或者 A 和 B 重叠而没有是另一个的子范围）。

如果范围 B ( B.upper_value - B.low_value) 的宽度至少是范围 A 的宽度，则 B 不能是 A 的严格子范围。因此，通过增加范围的宽度来对列表进行排序就足够了。这可以通过计算宽度然后进行基数排序在线性时间（假设固定大小的整数）内完成。

于 2014-01-19T07:36:02.127 回答