algorithm - 模糊排序区间，具有次要排序标准

Question

我想根据两个标准对项目列表进行排序。每个项目都包含一个间隔和一个数字。

Items[0] = {Interval=[10..30], Number = 7}
Items[1] = {Interval=[20..40], Number = 5}
Items[2] = {Interval=[30..50], Number = 3}
Items[3] = {Interval=[40..60], Number = 2}

我想根据间隔“模糊排序”这个列表：一个较早项目的区间下限不大于后一个项目的区间上限的顺序。

比如items[3]不应该排在前面items[0]，因为[40..60]严格大于[10..30]。但items[1]可能发生在 之前或之后items[0]，因为它们的间隔重叠。

因此，可以通过按下限、上限、中点或每个区间内的任意数字进行排序来实现有效的排序。

从所有这些可能的排序中，我想选择一个排序Number作为第二个标准的排序。对于所有可以交换的项目，因为它们的间隔重叠，我想交换它们，以便 Item.Number 递增。

因此，以下将是一个有效的顺序，按Interval升序排序，然后按Number升序排序：

Items[2] = {Interval=[30..50], Number = 3}
Items[1] = {Interval=[20..40], Number = 5}
Items[0] = {Interval=[10..30], Number = 7}
Items[3] = {Interval=[40..60], Number = 2}

有多个同样有效的解决方案。这也是使用相同标准的有效订单：

Items[0] = {Interval=[10..30], Number = 7}
Items[3] = {Interval=[40..60], Number = 2}
Items[2] = {Interval=[30..50], Number = 3}
Items[1] = {Interval=[20..40], Number = 5}

除了蛮力之外，是否有一种有效的算法来找到这样的排序？

这种类型或排序有名称吗？

标签： algorithmsortinglanguage-agnosticintervals

Answer 1

制作一个图，其中每个顶点都是一个区间。

对于每一对顶点：如果它们不重叠，则在它们之间添加一条从早到晚的有向边。

^{通过遍历所有对，我们可能会避免 O(n²) 的运行时间。如果我们按结束时间对间隔进行排序，按此顺序遍历间隔将使我们能够快速找到与遇到的任何给定间隔重叠的所有间隔（我们可以在此列表中查找该间隔开始之前的最新结束时间时间）。然后我们需要弄清楚如何避免创建任何不必要的边缘 - 对于 [1,2]、[3,4] 和 [5,6]，在 [1,2] 和 [5] 之间会有不必要的边缘,6]，因为它们通过 [3,4] 连接。}

边表示在我们的排序列表中哪些区间需要在哪些区间之前。

直到没有剩下的顶点，选择一个没有传入边的顶点。使它成为我们排序列表中的下一个元素，并删除该顶点的所有出边。

对于上述情况，如果我们将所有没有传入边的顶点放入按 排序的集合中Number，我们可以选择每个点的最小值来强制执行二级排序标准。

这将是 O(n²)，但也许可以优化为 O(n log n)。

---

举个例子：

Items[0] = {Interval=[10..30], Number = 7}
Items[1] = {Interval=[20..40], Number = 5}
Items[2] = {Interval=[30..50], Number = 3}
Items[3] = {Interval=[40..60], Number = 2}

图中唯一的边是 [10, 30] → [40, 60]。

这意味着我们可以选择除 [40, 60] 之外的任何顶点。

我们首先选择 [30, 50]，因为它在其余元素（3 < 5 和 3 < 7）之间具有最小的数字。

然后我们会选择 [20, 40]，因为 5 < 7。

然后我们会选择 [10, 30] 并将边缘移除到 [40, 60]，这将允许我们选择 [40, 60]。

最后我们会选择 [40, 60]。