数据结构来存储时间间隔并允许快速删除？

Question

我的一个朋友在面试中被问到了以下问题:你需要设计一个数据结构来存储ID为1:{1,5}，2:{2，10}，3:{4，20}的间隔...给定一个值x，您应该能够尽可能快地删除包含x的间隔。

例如，如果x= 3，则应同时删除1:{1,5}和2:{2,10}。

这很容易在线性时间内完成，所以我猜面试官正在寻找log(N)解。

Answer 1

解决方案1，快速删除(log(n))

将区间分解成更小的、不相交的区间(例如1:{1,5}，2:{2，10}，3:{4，20}变成{1,2} {2,4} {4,5} {5,20}；

用NewInterval X OrginalInterval中的边构建干涉图，其中(a，b)表示新的区间a包含在原始区间b中；

删除过程:对于给定的x，找到包含x( log，因为新的间隔可以排序)的新间隔，将该新间隔标记为已删除。

要列出结构的内容(未删除的间隔)：迭代未删除的新间隔，并收集相关的原始间隔。

解决方案2，对于快速插入新间隔( Log (n) )，缓慢删除(N)：实现对数时间的简单方法是使用两个二叉树。一个是使用区间的最小值，另一个是使用最大值。删除将“2Log(N)”

Find all the interval with min < x log(n)
Find all the interval with max > x log(n)
Intersect the two previous set (n)