algorithm - 查找 "circular"范围的重叠

Question

循环是指一个范围可以越过最大值并从 0 开始循环。例如:

给定一个最大值:

9 

还有两个范围(都可以是“循环的”):

0123456789
----range1 (a normal range)  
ge2----ran (a circular range)

什么是计算它们交集的好算法？ 在这种情况下，交叉点将是:

7-9 
789
ge1
ran

可以从另一个中“删除”一个算法的奖励。 我所说的删除是指一个范围完全从另一个范围中提取出来:

0123456789
----range1
ge2----ran

从范围 1 中减去范围 2 会产生:

3456
-ran

更新:数字总是整数。一次只比较两个范围，并且它们总是连续的，但如前所述，它们可能跨越 0。

另请注意，如果一个范围完全包含另一个范围，则输出一个 bool 值会很好。我想我可能有一个很好的方法来做到这一点。

谢谢!

Answer 1

看起来好像您可以简单地将范围中的每个离散元素放入一个集合中。然后，您可以执行集的交集以获取输出元素。

这可以通过使用哈希表在 O(M+N) 时间内完成。

遍历您的第一个范围，为范围内的每个元素在哈希表中创建一个条目。

然后遍历第二个范围并向上查找每个元素。如果它已经在哈希表中，那么它是范围交集的一部分。

稍加思考，您就会弄清楚集合差分是如何工作的。

如果您需要与第三个范围相交，请从表中删除不属于第二个范围的元素。