题目描述

给出一个非负整数的数据流 $a_1, a_2, … a_n, … $，请将它们动态地维护成一系列不相交的区间。

思考题： 假设有非常多的区间合并操作，并且区间总数远小于所有数的个数时，该怎么做？

样例

给定数据流：1, 3, 7, 2, 6, ..., 动态得到的区间是：
[1, 1]
[1, 1], [3, 3]
[1, 1], [3, 3], [7, 7]
[1, 3], [7, 7]
[1, 3], [6, 7]

算法

(平衡树) addNum: $O(logn)$, getIntervals: $O(n)$

我们用 map<int,int> L, R 来动态维护所有区间，L可以从区间右端点索引到左端点，R可以从区间左端点索引到右端点。
举例来说，假设有个区间是[x, y]，则L[y] = x并且R[x] = y。

对于addNum(val)操作：

1. 我们先判断val是否已经包含在某个区间中。具体来说，先用upper_bound(val)找出最后一个左端点小于等于val的区间，然后判断该区间的右端点是否大于等于val。
2. 如果val不包含在任何区间中，则分别判断val-1和val+1是否存在：
   • 如果都存在，则合并左右区间，合并方式：R[L[val - 1]] = R[val + 1]，L[R[val + 1]] = L[val - 1]，然后将R[val+1]和L[val-1]删除；
   • 如果只有一边存在，则将val插入该区间中；
   • 如果都不存在，则将val表示成一个单独的区间；

对于getIntervals()操作，直接输出所有区间即可。

时间复杂度分析：对于addNum操作，只涉及常数次平衡树的增删改查操作，所以时间复杂度是 $O(logn)$。对于getIntervals操作，需要将整棵平衡树遍历一遍，所以时间复杂度是 $O(n)$。

C++ 代码

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class SummaryRanges {
public:
    /** Initialize your data structure here. */
    map<int,int>L, R;
    SummaryRanges() {

    }

    void addNum(int val) {
        if (R.size())
        {
            auto it = R.upper_bound(val);
            if (it != R.begin())
            {
                -- it;
                if (it->second >= val) return;
            }
        }
        int right = R.count(val + 1), left = L.count(val - 1);
        if (left && right)
        {
            R[L[val - 1]] = R[val + 1];
            L[R[val + 1]] = L[val - 1];
            R.erase(val + 1), L.erase(val - 1);
        }
        else if (right)
        {
            L[R[val + 1]] = val;
            R[val] = R[val + 1];
            R.erase(val + 1);
        }
        else if (left)
        {
            R[L[val - 1]] = val;
            L[val] = L[val - 1];
            L.erase(val - 1);
        }
        else
        {
            R[val] = val;
            L[val] = val;
        }
    }

    vector<Interval> getIntervals() {
        vector<Interval> res;
        for (auto &p : R) res.push_back(Interval(p.first, p.second));
        return res;
    }
};

/**
 * Your SummaryRanges object will be instantiated and called as such:
 * SummaryRanges obj = new SummaryRanges();
 * obj.addNum(val);
 * vector<Interval> param_2 = obj.getIntervals();
 */