在各种系统设计中，高效地管理和操作数值区间是一项常见的挑战。例如，在一个任务调度系统中，需要跟踪特定时间段内的资源占用情况；在一个数据库索引中，可能需要快速查询某个范围内的键值。本篇文章将探讨如何设计一个区间管理器，使其能够支持高效地添加、查询和移除数值范围。

问题描述

我们需要实现一个名为 `RangeModule` 的模块，该模块能够跟踪一系列半开区间 `[left, right)`（包含 `left` 但不包含 `right`）。具体地，它需要支持以下三种操作：

• addRange(int left, int right)：添加区间 [left, right) 到模块中。如果新区间与已有区间重叠，它们应被合并。
• queryRange(int left, int right)：查询区间 [left, right) 中的所有实数是否都被当前模块跟踪。如果是，返回 true；否则，返回 false。
• removeRange(int left, int right)：从模块中移除区间 [left, right)。如果一个被跟踪的区间与移除区间重叠，它可能会被分割或部分移除。

示例

// 初始状态：无任何区间被跟踪
addRange(10, 20); // 模块跟踪区间 [10, 20)
removeRange(14, 16); // 模块跟踪区间 [10, 14) 和 [16, 20)
queryRange(10, 14); // 返回 true (区间 [10, 14) 完全被跟踪)
queryRange(13, 15); // 返回 false (例如 14, 14.5 等不在被跟踪范围内)
queryRange(16, 17); // 返回 true (区间 [16, 17) 完全被跟踪)

所有操作中的 `left` 和 `right` 满足 `0 < left < right < 10^9`。

解决方案分析

为了高效地执行这些区间操作，我们需要一个能够自动维护区间排序和支持快速查找的数据结构。Java 中的 TreeMap 是一个非常合适的选择。我们可以使用 TreeMap<Integer, Integer> 来存储区间，其中键表示区间的起始点，值表示区间的结束点。由于 `TreeMap` 自动按键排序，并且能够提供 `floorEntry()`、`tailMap()` 等方法来高效地查找和遍历区间，因此它非常适合处理这种区间合并、查询和分割的场景。

数据结构选择：TreeMap

我们将使用 `TreeMap managedIntervals;` 作为核心数据结构，其中键 `start` 映射到值 `end`，表示一个被跟踪的半开区间 `[start, end)`。`TreeMap` 的性质保证了所有存储的区间是按起始点有序的，并且由于我们只存储不重叠的区间，这个结构能够清晰地表示当前被跟踪的数值范围。

具体实现

1. 构造函数

构造函数只需初始化 `TreeMap`。

public class RangeModule {
    private TreeMap<Integer, Integer> managedIntervals;

    public RangeModule() {
        managedIntervals = new TreeMap<>();
    }
    // ... 其他方法
}

2. 添加区间 (addRange)

addRange(int newStart, int newEnd) 方法的目标是将 `[newStart, newEnd)` 添加到 `managedIntervals` 中。它需要处理与现有区间重叠的情况，将所有重叠的区间合并成一个更大的区间。

核心思路：

1. 初始化一个合并后的区间 `[mergedStart, mergedEnd)`，初始值为 `[newStart, newEnd)`。
2. 查找可能与 `newStart` 之前的现有区间重叠的区间。使用 `floorEntry(newStart)` 找到小于或等于 `newStart` 的最大键对应的区间。如果这个区间 `[s, e)` 满足 `e >= newStart`，则说明它们重叠，将 `mergedStart` 更新为 `min(s, newStart)`，`mergedEnd` 更新为 `max(e, newEnd)`，并将 `[s, e)` 从 `managedIntervals` 中移除。
3. 遍历从 `mergedStart` 开始的所有后续区间。如果某个区间 `[s', e')` 与当前的 `[mergedStart, mergedEnd)` 重叠（即 `s' <= mergedEnd`），则将其与 `[mergedStart, mergedEnd)` 合并，更新 `mergedEnd` 为 `max(mergedEnd, e')`，并移除 `[s', e')`。
4. 将最终合并后的 `[mergedStart, mergedEnd)` 添加到 `managedIntervals` 中。

public void addRange(int newStart, int newEnd) {
    int currentMergedStart = newStart;
    int currentMergedEnd = newEnd;

    // 1. 查找可能从左侧与新区间重叠的现有区间
    // 找到键 <= newStart 的最大 Entry
    Map.Entry<Integer, Integer> previousEntry = managedIntervals.floorEntry(newStart);
    if (previousEntry != null) {
        // 如果 previousEntry 的结束点 >= newStart (即存在重叠)
        if (previousEntry.getValue() >= newStart) {
            currentMergedStart = Math.min(currentMergedStart, previousEntry.getKey());
            currentMergedEnd = Math.max(currentMergedEnd, previousEntry.getValue());
            managedIntervals.remove(previousEntry.getKey()); // 移除旧的重叠区间
        }
    }

    // 2. 遍历并合并从 currentMergedStart 开始的所有后续重叠区间
    // tailMap(currentMergedStart) 返回一个视图，其键 >= currentMergedStart
    Iterator<Map.Entry<Integer, Integer>> iterator = managedIntervals.tailMap(currentMergedStart).entrySet().iterator();
    while (iterator.hasNext()) {
        Map.Entry<Integer, Integer> currentSegment = iterator.next();
        // 如果当前段的起始点 <= currentMergedEnd (即存在重叠)
        if (currentSegment.getKey() <= currentMergedEnd) {
            currentMergedEnd = Math.max(currentMergedEnd, currentSegment.getValue()); // 扩展合并区间的右边界
            iterator.remove(); // 移除当前重叠段
        } else {
            // 当前段的起始点在 currentMergedEnd 之后，没有更多重叠了
            break;
        }
    }

    // 3. 将最终合并后的区间添加回 TreeMap
    managedIntervals.put(currentMergedStart, currentMergedEnd);
}

3. 查询区间 (queryRange)

queryRange(int queryStart, int queryEnd) 方法需要判断 `[queryStart, queryEnd)` 是否完全包含在一个已跟踪的区间内。

核心思路：

1. 查找在 `queryStart` 之前或等于 `queryStart` 的最大键对应的区间。
2. 如果找到了这样的区间 `[s, e)`，并且它的结束点 `e` 大于或等于 `queryEnd`，则说明 `[s, e)` 完全覆盖了 `[queryStart, queryEnd)`。返回 `true`。
3. 否则，返回 `false`。

public boolean queryRange(int queryStart, int queryEnd) {
    // 查找键 <= queryStart 的最大 Entry
    Map.Entry<Integer, Integer> segment = managedIntervals.floorEntry(queryStart);
    
    // 如果没有找到这样的 Entry，或者找到的 Entry 无法覆盖 queryStart
    if (segment == null || segment.getKey() > queryStart) { // segment.getKey() > queryStart should not happen with floorEntry
        return false;
    }
    
    // 检查找到的区间是否完全覆盖 [queryStart, queryEnd)
    return segment.getValue() >= queryEnd;
}

4. 移除区间 (removeRange)

removeRange(int removeStart, int removeEnd) 方法的目标是从 `managedIntervals` 中移除 `[removeStart, removeEnd)`。这个操作可能会导致一个现有区间被分割成两个，或者部分被移除。

核心思路：

1. 初始化两个列表：一个用于存储移除操作后需要重新插入的区间 `(newSegmentsToInsert)`，另一个用于存储需要从 `managedIntervals` 中移除的旧区间键 `(keysToRemove)`。
2. 处理可能与 `removeStart` 左侧重叠的区间：查找键小于或等于 `removeStart` 的最大键对应的区间 `[s, e)`。如果 `e > removeStart`，则表示这个区间与 `[removeStart, removeEnd)` 重叠。
   • 如果 `s < removeStart`，则 `[s, removeStart)` 这一部分仍然保留，添加到 `newSegmentsToInsert`。
   • 如果 `e > removeEnd`，则 `[removeEnd, e)` 这一部分仍然保留，添加到 `newSegmentsToInsert`。
   将 `s` 添加到 `keysToRemove`。
3. 遍历所有从 `removeStart` 开始且可能与 `[removeStart, removeEnd)` 重叠的后续区间。对于每个这样的区间 `[s', e')`：
   • 如果 `s' >= removeEnd`，则表示没有更多重叠，停止遍历。
   • 将 `s'` 添加到 `keysToRemove`。
   • 如果 `e' > removeEnd`，则 `[removeEnd, e')` 这一部分仍然保留，添加到 `newSegmentsToInsert`。
4. 最后，先从 `managedIntervals` 中移除所有 `keysToRemove` 中的键，然后将 `newSegmentsToInsert` 中的所有区间添加回 `managedIntervals`。

public void removeRange(int removeStart, int removeEnd) {
    List<int[]> newSegmentsToInsert = new ArrayList<>();
    Set<Integer> keysToRemove = new HashSet<>();

    // 1. 处理可能从左侧与移除区间重叠的现有区间
    Map.Entry<Integer, Integer> floorSegment = managedIntervals.floorEntry(removeStart);
    if (floorSegment != null) {
        if (floorSegment.getValue() > removeStart) { // 如果存在重叠
            // 左侧剩余部分
            if (floorSegment.getKey() < removeStart) {
                newSegmentsToInsert.add(new int[]{floorSegment.getKey(), removeStart});
            }
            // 右侧剩余部分
            if (floorSegment.getValue() > removeEnd) {
                newSegmentsToInsert.add(new int[]{removeEnd, floorSegment.getValue()});
            }
            keysToRemove.add(floorSegment.getKey()); // 标记旧区间为待移除
        }
    }

    // 2. 遍历并处理所有从 removeStart 之后开始并与移除区间重叠的区间
    // tailMap(removeStart) 返回一个视图，其键 >= removeStart
    Iterator<Map.Entry<Integer, Integer>> iterator = managedIntervals.tailMap(removeStart).entrySet().iterator();
    while (iterator.hasNext()) {
        Map.Entry<Integer, Integer> currentSegment = iterator.next();
        if (currentSegment.getKey() >= removeEnd) { // 当前区间在 removeEnd 之后，没有更多重叠
            break;
        }
        // 当前区间与 [removeStart, removeEnd) 重叠
        keysToRemove.add(currentSegment.getKey()); // 标记当前区间为待移除
        
        // 如果当前区间延伸到 removeEnd 之外，则保留其右侧部分
        if (currentSegment.getValue() > removeEnd) {
            newSegmentsToInsert.add(new int[]{removeEnd, currentSegment.getValue()});
        }
    }

    // 3. 执行移除和插入操作
    for (Integer key : keysToRemove) {
        managedIntervals.remove(key);
    }
    for (int[] segment : newSegmentsToInsert) {
        managedIntervals.put(segment[0], segment[1]);
    }
}