javascript - "circular"区间树算法

Question

我想知道是否有人已经实现/知道(最好是 javascript)将处理循环间隔的间隔树算法。通过循环，我的意思是开始 > 结束的间隔。请注意，这也需要限制间隔的大小。

这只是常见区间树问题的一个子案例吗？

针对评论中提出的问题:这是我所说的圆形子范围的图像(感谢 G. Bach 和维基百科):

并且(与上图无关)这是范围的示例 json 表示:[{id: 'range1', start: 3, end: 34}, {id: 'range2circular', start: 30, end:6}]

希望

谢谢!

Answer 1

与背后想法相关的声音 circular arc graphs (但不是图表本身，因为您从间隔开始并且不关心它们的圆弧图表示)。

假设是这样，这意味着域可以用类似于圆的度数的周期表示。然后你有一个最小可能值 min 和一个最大可能值 max = min + 1*period，你要做的第一件事就是找到最小的 s 这样 start = min + s + k*period 对于整数 k (基本上，这是一个模运算)，同样你找到最小的 e 这样 end = min + e + j*period。

现在您可以将间隔表示为 (s,e) 仍然是 s > e。将它分成两个区间 (s, max) 和 (min, e)，将它们放入你的区间树中，并为它们提供对你原始区间的引用(开始，结束)。如果您从可能与周期重叠的 n 区间开始，您将在树中以 2n 区间结束，并且渐近边界成立。