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

A friend of mine was asked the following question during interview: You need to design a data structure that stores intervals with an ID like 1:{1,5}, 2:{2, 10}, 3:{4, 20} ... and given a val x, you should be able to delete intervals that contain x as fast as possible.

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

For example, if x = 3, both 1:{1,5} and 2:{2,10} should be deleted.

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

It's easy to do it in linear time, so I guess the interviewer is looking for log(N) solution.

这很容易在线性时间内完成，所以我猜访问者正在寻找log（N）解决方案。

1 个解决方案

#1

Solution 1 , fast deletion (log(n))

解决方案1，快速删除（log（n））

Break down the intervals into smaller, disjoint intervals (Eg 1:{1,5}, 2:{2, 10}, 3:{4, 20} becomes {1,2} {2,4} {4,5} {5,20};

将间隔细分为较小的，不相交的间隔（例如1：{1,5}，2：{2,10}，3：{4,20}变为{1,2} {2,4} {4,5} {5,20};

Build an interference graph with Edge in [NewInterval X OrginalInterval] where (a,b) means that the new interval a is included in the orginal interval b;

在[NewInterval X OrginalInterval]中使用Edge构建干扰图，其中（a，b）表示新区间a包含在原始区间b中;

Deletion procedure : For a given x, find the new interval which included x ( log n, since the new intervals can be sorted) Marks that new interval as deleted.

删除过程：对于给定的x，找到包含x的新间隔（log n，因为新的间隔可以排序）将新间隔标记为已删除。

To list the content of the structure ( non deleted intervals) : Iterate over the non deleted new intervals, and collects the associated orignal intervals .

列出结构的内容（未删除的间隔）：迭代未删除的新间隔，并收集关联的orignal间隔。

Solution 2 , for fast insertion of new intervals (log(n)), slow deletion (n) : A simple way to achieve Log time would be to use two binary trees. One where you use the min of the interval, the other where you use the max. Deletion would '2Log(N)'

解决方案2，用于快速插入新间隔（log（n）），慢删除（n）：实现Log time的一种简单方法是使用两个二叉树。一个你使用间隔的最小值，另一个你使用最大值。删除'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)

#1