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}

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

这个类型或类别有名称吗？

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]。