我的一个 friend 在面试中被问到以下问题: 您需要设计一个数据结构来存储具有 ID 的间隔，例如 1:{1,5}, 2:{2, 10}, 3:{4, 20} ... 并给定一个 val x，您应该能够尽快删除包含 x 的区间。
例如，如果 x = 3，则应删除 1:{1,5} 和 2:{2,10}。
在线性时间内很容易做到，所以我猜面试官正在寻找 log(N) 的解决方案。
最佳答案
方案一，快速删除(log(n))
将区间分解成更小的、不相交的区间(例如 1:{1,5}, 2:{2, 10}, 3:{4, 20} 变成 {1,2} {2,4} {4 ,5} {5,20};
在[NewInterval X OrginalInterval]中用Edge建立干扰图 其中(a,b)表示新的区间a包含在原来的区间b中；
删除程序: 对于给定的 x，找到包含 x 的新区间(log n，因为新区间可以排序) 将该新间隔标记为已删除。
要列出结构的内容(非删除间隔): 迭代未删除的新区间，并收集关联的原始区间。
方案二，快速插入新区间(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)
关于algorithm - 存储间隔并允许快速删除的数据结构？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31225425/