sorting - 需要异常排序算法

Question

我有一个包含大约 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)。

谢谢，标记

Answer 1

我的第一 react 是它听起来像 topological sort ，其中范围被视为图中的节点，并且认为从范围 A 到范围 B 存在一条边当且仅当 A 是 B 的子范围。

我假设你的意思是输出列表的条件是如果 A 出现在 B 之前，那么 B 不是 A 的严格子集(但如果 A = B，A 和 B 不相交，或者 A 和 B重叠而不是另一个的子范围)。

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