LeetCode 第 352 题 “数据流中的不相交区间” (Summary Ranges) 要求设计一个数据结构，能够接收整数数据流，并随时将当前已接收的所有数字合并为若干个不相交的区间列表。

核心思路

我们需要维护一个有序的区间列表。每当插入一个新的数字 val 时，主要考虑它与现有区间的关系：
独立成段：val 与任何现有区间都不相邻（即 val end+1），则创建新区间 [val, val]。
合并左侧：val 恰好是某个区间左端点减 1 (val == start - 1)，则将该区间左端点扩展为 val。
合并右侧：val 恰好是某个区间右端点加 1 (val == end + 1)，则将该区间右端点扩展为 val。
连接两侧：val 恰好填补了两个区间之间的空隙（即左边区间的 end + 1 == val 且右边区间的 start - 1 == val），则将这两个区间合并为一个，并包含 val。
已在区间内：val 已经存在于某个区间内部，无需操作。

为了高效地找到 val 可能相邻的区间，通常使用 有序集合 (如 C++ 的 std::map 或 Java 的 TreeMap) 来存储区间，键为区间的起始值，值为区间的结束值。这样可以在 O(log N) 的时间内定位到潜在的相关区间。

代码实现 (Java)

import java.util.*;

class SummaryRanges {
private TreeMap intervals;

public SummaryRanges() {
    intervals = new TreeMap();
}

public void addNum(int val) {
    // 查找大于等于 val 的第一个区间
    Map.Entry higher = intervals.ceilingEntry(val);
    
    // 检查前一个区间是否包含 val
    Map.Entry lower = intervals.floorEntry(val);
    if (lower != null && lower.getValue() >= val) {
        return; // 已经在区间内
    }

    boolean mergeLeft = false;
    boolean mergeRight = false;
    int leftStart = val;
    int rightEnd = val;

    // 检查左侧
    if (lower != null && lower.getValue() + 1 == val) {
        mergeLeft = true;
        leftStart = lower.getKey();
    }

    // 检查右侧
    if (higher != null && higher.getKey() - 1 == val) {
        mergeRight = true;
        rightEnd = higher.getValue();
    }

    if (mergeLeft && mergeRight) {
        // 合并左右
        intervals.put(leftStart, rightEnd);
        intervals.remove(higher.getKey());
    } else if (mergeLeft) {
        // 合并左
        intervals.put(leftStart, val);
    } else if (mergeRight) {
        // 合并右
        intervals.put(val, rightEnd);
        intervals.remove(higher.getKey());
    } else {
        // 独立
        intervals.put(val, val);
    }
}

public int[][] getIntervals() {
    List result = new ArrayList();
    for (Map.Entry entry : intervals.entrySet()) {
        result.add(new int[]{entry.getKey(), entry.getValue()});
    }
    return result.toArray(new int[result.size()][]);
}

}

复杂度分析

假设当前有 N 个不相交区间：

时间复杂度:
addNum: 主要消耗在 TreeMap/map 的查找、插入和删除操作上，均为 O(log N)。
getIntervals: 需要遍历所有区间，复杂度为 O(N)。
空间复杂度: O(N)，用于存储所有的区间。

示例演示

假设输入流为: 1, 3, 7, 2, 6

Add 1: 区间 {[1, 1]}
Add 3: 3 与 1 不相邻。区间 {[1, 1], [3, 3]}
Add 7: 7 与 3 不相邻。区间 {[1, 1], [3, 3], [7, 7]}
Add 2:
2 与 [1, 1] 相邻 (1+1=2)。
2 与 [3, 3] 相邻 (3-1=2)。
合并三者：[1, 1] + 2 + [3, 3] -> [1, 3]。
区间变为 {[1, 3], [7, 7]}
Add 6:
6 与 [7, 7] 相邻 (7-1=6)。
合并：[6, 7]。
区间变为 {[1, 3], [6, 7]}

最终 getIntervals() 返回 [[1, 3], [6, 7]]。