排序循环/周期间隔



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

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

在示例中,数组将是(1 乞求,2 乞求,5 端,6 端,10 端,12 乞求,17 端(

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

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

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

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

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

相关内容

  • 没有找到相关文章