数据流中的不相交区间如何动态维护？新数字如何合并左右邻居？

简化版

数据流维护不相交区间可以用 TreeMap，key 为区间起点。加入数字 val 时，找到起点不大于 val 的左区间和起点大于 val 的右区间。若 val 已在左区间内则忽略；否则看它是否能和左区间、右区间相邻并合并。

详细版

TreeMap 支持 floorEntry(val) 找左邻居，ceilingEntry(val) 找右邻居。插入时有四种情况：已被覆盖、同时连接左右区间、只连接左区间、只连接右区间、单独成新区间。合并时要删除旧右区间，并更新左区间终点或新增起点。

每次插入复杂度 O(log n)，获取区间按起点顺序输出即可。关键是处理相邻条件：左区间 end + 1 == val，右区间 start - 1 == val。

完整版教学

一、为什么不能每次重新排序整个数据流

数据流会不断加入数字，如果每次 getIntervals() 都把所有数字排序再合并，插入多、查询多时成本很高。更自然的方式是始终维护已经合并好的不相交区间。

add 1 => [1,1]
add 3 => [1,1], [3,3]
add 2 => [1,3]

这个过程需要动态找某个数字附近的区间，所以有序映射很合适。

二、TreeMap 存什么

用区间起点作为 key，区间终点作为 value：

start -> end

例如：

1 -> 3
7 -> 9

表示当前区间是 [1,3] 和 [7,9]。由于区间不相交且按起点排序，找左右邻居就能判断是否合并。

三、插入 val 时要找哪两个邻居

插入 val 只可能影响它左边最近的区间和右边最近的区间，不可能影响更远的区间。

邻居	TreeMap 操作	用途
左区间	`floorEntry(val)`	判断是否覆盖或左相邻
右区间	`ceilingEntry(val)`	判断是否右相邻

记忆钩子：动态区间插入一个点，只看左右邻居，别扫全表。

如果左区间已经覆盖 val，说明这个数字重复加入，直接忽略。

四、四种合并情况

假设左区间是 [ls,le]，右区间是 [rs,re]。

1. le >= val：已覆盖，忽略
2. le + 1 == val 且 val + 1 == rs：左右桥接，合并为 [ls,re]
3. le + 1 == val：扩展左区间为 [ls,val]
4. val + 1 == rs：扩展右区间为 [val,re]
5. 否则：新增 [val,val]

桥接情况最容易漏。比如已有 [1,2] 和 [4,5]，加入 3 后必须变成 [1,5]。

五、代码模板

class SummaryRanges {
    private final TreeMap<Integer, Integer> map = new TreeMap<>();

    public void addNum(int val) {
        Map.Entry<Integer, Integer> left = map.floorEntry(val);
        if (left != null && left.getValue() >= val) return;

        Map.Entry<Integer, Integer> right = map.ceilingEntry(val);
        boolean mergeLeft = left != null && left.getValue() + 1 == val;
        boolean mergeRight = right != null && right.getKey() - 1 == val;

        if (mergeLeft && mergeRight) {
            map.put(left.getKey(), right.getValue());
            map.remove(right.getKey());
        } else if (mergeLeft) {
            map.put(left.getKey(), val);
        } else if (mergeRight) {
            int end = right.getValue();
            map.remove(right.getKey());
            map.put(val, end);
        } else {
            map.put(val, val);
        }
    }
}

输出时遍历 map.entrySet()，每个 entry 转成 [start,end]。

六、用例子推演

加入序列 1,3,7,2,6：

1 => [1,1]
3 => [1,1], [3,3]
7 => [1,1], [3,3], [7,7]
2 => 桥接 [1,1] 和 [3,3]，得到 [1,3], [7,7]
6 => 连接右侧 [7,7]，得到 [1,3], [6,7]

每次只看左右两个邻居，就能维护全局不相交。

七、常见误区与追问

误区：插入时遍历所有区间。 有序映射能直接定位左右邻居，没必要全扫。
误区：忘记处理重复数字。 如果 val 已在左区间内，应直接返回。
误区：桥接时只扩展一边。 [1,2] + 3 + [4,5] 必须合并成一个区间。
追问：为什么用起点做 key？ 起点有序能用 floor/ceiling 找相邻区间。
追问：每次 add 复杂度是多少？ TreeMap 查找和更新都是 O(log n)。
追问：如果批量离线处理呢？ 可以排序所有数字再一次性合并，动态场景才需要 TreeMap。

八、加强记忆

数据流区间维护记住“起点有序、左右邻居”。新数字只可能被左区间覆盖、连接左区间、连接右区间、桥接左右，或自己成段。TreeMap 的 floorEntry 和 ceilingEntry 正好对应这两个邻居，桥接时别忘了删除旧右区间。

简化版

详细版