algorithm - 如何测试整数范围是否与整数列表重叠？

Question

例如:我们有一个列表:

1 2 3 7 8 9 11 12

我们需要检查范围 (A,B) 是否与列表重叠，例如范围 (4, 6) 不与列表重叠，范围 (10, 12) 和范围(5,9) 与列表重叠列表。我知道我们可以将列表放在 hashSet 中，然后我们只检查范围内的任何元素是否出现在该集合中。这花费了 O(N)。 N 是范围的长度。有没有更好的算法来解决这个问题？我知道有一个区间树数据结构，但我不是很明白。那个结构能解决logN中的这个问题吗？

Answer 1

列表似乎已排序；如果还没有，则先对其进行排序。

设 R = (start, end) 为我们要检查的范围，看它是否重叠。

我们可以二分查找start和end在排序列表中的位置:

• 如果 start 和 end 连续出现在列表中，则它们不会重叠

例如

1 2 3 4 6 7 8 9 11 12

• 否则，列表中有一个元素位于它们之间，因此范围重叠

请看:

1 2 3 7 8 9 10 11 12

这是 O(log N)，其中 N 是列表中元素的数量。