如何有效地合并流中的int范围？

Question

我们给出了连续的整数范围流,如[1,3],[5,10],[2,6],...当每个新范围到来时,我们需要检查现有范围并查看它是否与任何现有范围,如果发现任何重叠,则删除所有重叠范围,并插入合并范围.我们需要一种有效的算法.请注意,范围一次一个,形成一个流......

在接受采访时被问到这个问题.想法？

目的是将重叠范围合并为一个.例如,如果我们有3个范围按以下顺序排列:[1,3],[2,6],[5,10].然后我们首先将前两个合并为[1,6],然后与第三个合并,它变为[1,10].

Answer 1

此问题的标准算法是间隔树.

Answer 2

当一个新的元组进入时，在现有的结束元素列表中(newstart,newend)执行二分搜索 fon ，并且在现有的开始元素列表中执行类似的 for 。newstart-1newend+1

与任何匹配范围合并。

如果没有范围匹配，则在两个最接近的范围之间插入。

更新：从头开始，我正在解决错误的问题：合并接触范围。但重叠范围解决方案不会太不同。

1. 二分查找最大的现有起始元素，其中start(n) <= newstart
2. 二分查找最小的现有结束元素，其中end(n) >= newstart
3. 如果两者返回相同的索引，则您的元组开头可与第 n 个条目合并，替换newstart为start(n)
4. 二分查找最大的现有起始元素，其中start(m) <= newend
5. 二分查找最小的现有结束元素，其中end(m) >= newend
6. 如果两者返回相同的索引，则您的元组末尾可与第 m 个条目合并，替换newend为end(m)
7. 将第 n 个和第 m 个索引之间的所有条目替换为元(newstart,newend)组。