两种区间操作场景下增删、包含/覆盖查询的最优数据结构选型

前置定义 #

区间统一采用左闭右开格式[start, end)，对应类结构如下：

class Interval {
    int start, end;
}

场景一：插入自动合并区间场景 #

功能要求 #

需实现3个API，插入时自动合并重叠/相邻区间：

• void insert(Interval interval)：插入区间时自动合并重叠、相邻的区间，例如插入[1,4)、[3,6)、[9,12)后，内部仅存储[1,6)、[9,12)两个不重叠区间
• boolean contain(Interval interval)：判断合并后的整体区间是否完全覆盖入参区间，无需单个区间覆盖，例如contain([2,5))返回true，contain([4,7))返回false
• void remove(Interval interval)：从现有合并区间中移除指定区间段，例如移除[10,11)后，内部区间变为[1,6)、[9,10)、[11,12)

最优数据结构：基于区间start排序的有序平衡二叉搜索树（典型实现为Java TreeMap、C++ std::map） #

原因如下：
合并后的区间天然是不重叠、不相邻、按start严格递增排列的，我们可以将区间的start作为key，区间整体作为value存入平衡树：

1. 插入操作：仅需O(logn)时间即可定位到第一个start大于当前插入区间end的位置，向前遍历所有与插入区间重叠的区间完成合并，替换原有区间即可，均摊时间复杂度O(logn)
2. contain查询：O(logn)定位到第一个start小于等于查询区间start的区间，向后遍历连续的可衔接区间即可判断是否完全覆盖入参，均摊时间复杂度O(logn)
3. 移除操作：O(logn)定位到和待移除区间重叠的区间，切割重叠部分后将剩余的前后段重新存入即可，均摊时间复杂度O(logn)

场景二：保留原始插入区间场景 #

功能要求 #

插入时不合并，保留所有原始插入的区间，需实现4个API：

• void insert(Interval interval)：直接插入原始区间，不做合并
• boolean has(Interval interval)：判断是否存在和入参完全相同的区间，例如插入2次[1,4)后，has([1,4))返回true，has([1,2))返回false
• boolean cover(Interval interval)：判断是否存在单个原始区间可完全覆盖入参区间，不可通过多区间合并判断，例如cover([2,5))返回false，cover([2,3))返回true
• boolean remove(Interval interval)：仅删除一个和入参完全相同的区间，不存在则返回false，例如删除一次[1,4)后，剩余1个[1,4)、[3,6)、[9,12)

最优数据结构：哈希表 + 有序平衡二叉搜索树的组合结构 #

原因如下：
两类API的查询逻辑差异大，组合结构可以同时满足两类查询的效率要求：

1. 用哈希表Map<Pair<Integer, Integer>, Integer> countMap存储每个(start, end)区间的出现次数：insert、has、remove三个需要精确匹配区间的操作都可以O(1)时间完成，插入/删除时同步维护计数即可
2. 用有序平衡二叉搜索树TreeMap<Integer, Integer> startMaxEndMap存储所有不重复的start值，以及对应start下所有区间的最大end值，额外维护前缀最大end：处理cover查询时，O(logn)即可查询到所有start小于等于入参start的区间的最大end值，若该值大于等于入参的end则返回true，否则返回false，时间复杂度O(logn)

内容的提问来源于stack exchange，提问作者maplemaple