algorithm - 排序循环/周期性间隔

Question

我需要找到间隔的最大交点数，即对于 [1,6]、[2,5]、[5,10]、[12,17]，最大交点数为 5，即3.

现在这很容易做到，只需将数字标记为间隔的开始/结束并对它们进行排序(在平局的情况下有利于开始数字)然后遍历排序的数组并跟踪开始和结束的数量以及最大的差异这两者之间是最大值。

在这个例子中，数组是(1 beg,2 beg,5 beg,5 end,6 end,10 end,12 beg,17 end)

在 5 处有 3 个开始和 0 个结束。

现在我的问题是我的间隔是循环/周期性的，例如，如果间隔包含在 [0,1] 中，则 1 等于 0(就像绕一圈并返回同一点)间隔 [0.7 ,0.3] 可以想象为 [0.7,1] 和 [0,0.3] 的并集，所以它不同于 [0.3,0.7]。

该方法失败，因为例如第一个数字可能是结束数字。

Answer 1

您可以计算此类特殊间隔的数量(即开始值大于结束值的间隔)，并将此数字作为开始数量的初始值(而不是零)。

现在您可以像对待算法中的任何其他区间一样对待特殊区间并找到正确答案。