如何从连续运行的随机整数生成器中有效地找到整数簇的数目？

Question

有一个随机整数生成器，它生成随机整数，并在后台运行。需要设计一个API，该API在调用时返回集群的数量。

聚类:群集是连续整数的字典顺序。例如，在这种情况下，10，7，1，2，2，8，5，9组是3组(1，2-5-7，8，9，10)。

如何解决这个问题时，有数十亿或万亿个整数。什么是最优的解决方案？(请记住，生成器是在后台运行的，可以随时多次调用API )

我的方法:继续将整数从生成器插入到列表中。当调用API时，对列表进行排序(插入)，并遍历列表以找到集群的数量。但我认为这不是一个有效的方法。

Answer 1

一种间隔树怎么样。不是可以跟踪重叠间隔的标准间隔，而是只跟踪不相交间隔并自动合并重叠/相邻间隔的更简单的间隔。

一段间隔的BST，按开始排序。若要插入新的间隔，

1. 找出最高小于新间隔开始的值，如果它们是相邻的，就将它加入其中。
2. 取现在的间隔(插入的间隔或连接的间隔)，找出最低的--高于它的端点--如果相邻，就加入它们。
3. 如果您已加入两次，则删除第一个(较短)连接间隔。
4. 如果已加入零次，则将新间隔插入为新节点。
5. 应用通常的BST平衡旋转，如果有必要的话，以保持树至少在某种程度上的平衡

集群的数量在任何时候都是叶子的数量。您甚至不需要显式地计算它们，只需在更改树时更新计数即可。

插入是对数的集群数，他们的大小是无关的。这有一个有趣的副作用，对于随机整数，这会在一段时间内变慢，因为树必须继续表示大部分单位间隔，但是当有足够多的整数时，它又慢慢地开始变得更快，因为超出某个点的插入将倾向于加入比它们创建的更多的间隔。最后，对于树中的每个整数，它只剩下一个节点，表示跨越所有整数的单个集群。