Given a data stream input of non-negative integers a1, a2, ..., an, summarize the numbers seen so far as a list of disjoint intervals.

Implement the SummaryRanges class:


	SummaryRanges() Initializes the object with an empty stream.
	void addNum(int val) Adds the integer val to the stream.
	int[][] getIntervals() Returns a summary of the integers in the stream currently as a list of disjoint intervals [starti, endi].


&nbsp;
Example 1:

Input
["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"]
[[], [1], [], [3], [], [7], [], [2], [], [6], []]
Output
[null, null, [[1, 1]], null, [[1, 1], [3, 3]], null, [[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, [[1, 3], [6, 7]]]

Explanation
SummaryRanges summaryRanges = new SummaryRanges();
summaryRanges.addNum(1);      // arr = [1]
summaryRanges.getIntervals(); // return [[1, 1]]
summaryRanges.addNum(3);      // arr = [1, 3]
summaryRanges.getIntervals(); // return [[1, 1], [3, 3]]
summaryRanges.addNum(7);      // arr = [1, 3, 7]
summaryRanges.getIntervals(); // return [[1, 1], [3, 3], [7, 7]]
summaryRanges.addNum(2);      // arr = [1, 2, 3, 7]
summaryRanges.getIntervals(); // return [[1, 3], [7, 7]]
summaryRanges.addNum(6);      // arr = [1, 2, 3, 6, 7]
summaryRanges.getIntervals(); // return [[1, 3], [6, 7]]


&nbsp;
Constraints:


	0 &lt;= val &lt;= 104
	At most 3 * 104 calls will be made to addNum and getIntervals.


&nbsp;
Follow up: What if there are lots of merges and the number of disjoint intervals is small compared to the size of the data stream?

class SummaryRanges:
    def __init__(self):
        self.intervals = []
    def addNum(self, val: int) -> None:
        left, right = 0, len(self.intervals) - 1
        while left <= right:
            mid = (left + right) // 2
            e = self.intervals[mid]
            if e[0] <= val <= e[1]: return
            elif val < e[0]:right = mid - 1
            else:left = mid + 1
        pos = left
        self.intervals.insert(pos, [val, val])
        if pos + 1 < len(self.intervals) and val + 1 == self.intervals[pos+1][0]:
            self.intervals[pos][1] = self.intervals[pos+1][1]
            del self.intervals[pos+1]
        if pos - 1 >= 0 and val - 1 == self.intervals[pos-1][1]:
            self.intervals[pos-1][1] = self.intervals[pos][1]
            del self.intervals[pos]

    def getIntervals(self) -> List[List[int]]:
        return self.intervals
class SummaryRanges {

    Map<Integer, int[]> st;
    Map<Integer, int[]> end;
    Set<Integer> pending;
    int[][] prev = new int[0][];
    Set<Integer> seen = new HashSet<>();
    int INVALID = -1;
    public SummaryRanges() {
        st = new HashMap<>();
        end= new HashMap<>();
        pending = new HashSet<>();
    }

    public void addNum(int val) { // [TC: O(1)]
        if (!seen.contains(val)){ // only add if not seen.
            pending.add(val); // pending processing list
        }
    }

    public int[][] getIntervals() { // [TC: O(pending list length (= k)) best case (all merges), O(n)+O(klogk) worst case (all inserts)]
        Set<int[]> addSet = new HashSet<>();
        for (int n : pending){
            if (st.containsKey(n+1)&&end.containsKey(n-1)){ // merge intervals on both ends, a new interval form -> add to addSet
                int[] s = st.get(n+1);
                int[] e = end.get(n-1);
                int[] m = new int[]{e[0], s[1]};
                st.remove(n+1);
                end.remove(n-1);
                st.put(m[0], m);
                end.put(m[1], m);
                s[0]=e[0]=INVALID;
                addSet.remove(s); // may be in addSet, remove them
                addSet.remove(e);
                addSet.add(m);
            }else if (st.containsKey(n+1)){ // merge with the next interval, no other action required.
                st.get(n+1)[0]--;
                st.put(n, st.get(n+1));
                st.remove(n+1);
            }else if (end.containsKey(n-1)){ // merge with the previous interval, no other action required.
                end.get(n-1)[1]++;
                end.put(n, end.get(n-1));
                end.remove(n-1);
            }else{ // new interval -> add to AddSet
                int[] m = new int[]{n, n};
                addSet.add(m);
                st.put(n, m);
                end.put(n, m);
            }
        }

        seen.addAll(pending);
        pending.clear(); // remember to clear the pending list.

        if (!addSet.isEmpty()){ // IF there is no new intervals to insert, we SKIP this.
            List<int[]> addList = new ArrayList<>(addSet);
            addList.sort(Comparator.comparingInt(o -> o[0]));
            int i = 0, j = 0; // two pointers because both prev & addList are sorted.
            List<int[]> ans = new ArrayList<>();
            while(i < prev.length || j < addList.size()){
                if (i < prev.length && prev[i][0]==INVALID){
                    i++;
                }else if (j == addList.size() || i < prev.length && prev[i][0]<addList.get(j)[0]){
                    ans.add(prev[i++]);
                }else if (i == prev.length || prev[i][0]>addList.get(j)[0]){
                    ans.add(addList.get(j++));
                }
            }
            prev = ans.toArray(new int[0][]);
        }

        return prev;
    }
}
class SummaryRanges {
public:

    struct DSU {
        map<int, int>parent;
        map<int, int>sz;

        int find_parent(int a) {
            if(!parent.count(a)) {
                parent[a] = a;
                sz[a] = 1;
            }

            if(parent[a] == a) return a;
            return parent[a] = find_parent(parent[a]);
        }

        void union_sets(int a, int b) {
            if(!parent.count(a)) {
                parent[a] = a;
                sz[a] = 1;
            }

            if(!parent.count(b)) {
                parent[b] = b;
                sz[b] = 1;
            }


            a = find_parent(a);
            b = find_parent(b);

            if(a == b) return;

            parent[b] = a;
            sz[a] += sz[b];


        }

        void add(int a) {


            if(!parent.count(a)) {
                parent[a] = a;
                sz[a] = 1;
            } else return;



            if(parent.count(a + 1)) {
                union_sets(a, a + 1);
            }
            if(parent.count(a - 1)) {
                union_sets(a - 1, a);
            }
        }

        vector<vector<int>>getIntervals() {
            vector<vector<int>>intervals;
            for(auto [a, b]: parent) {
                if(a == b) {
                    intervals.push_back({a, a + sz[a] - 1});
                }
            }

            return intervals;
        }

    };
    
    DSU dsu;

    SummaryRanges() {
        this->dsu = DSU();
    }
    
    void addNum(int val) {
        dsu.add(val);
    }
    
    vector<vector<int>> getIntervals() {
        return dsu.getIntervals();
    }
};
var SummaryRanges = function() {
    this.tree = null // { val, left?, right? }
};

/** 
 * @param {number} val
 * @return {void}
 */
SummaryRanges.prototype.addNum = function(val) {
    if (!this.tree) {
        this.tree = { val }
    } else {
        let node = this.tree
        let parent, side
        while (node) {
            if (node.val === val) { return }
            parent = node
            side = node.val > val ? 'left' : 'right'
            node = node[side]
        }
        parent[side] = { val }
    }
};

/**
 * @return {number[][]}
 */
SummaryRanges.prototype.getIntervals = function() {
    // travel from left to right
    // generate intervals
	// > (x === last[1] + 1) ? update last[1] : create a new one
    const travel = (node, check) => {
        if (!node) { return }
        travel(node.left, check)
        check(node.val)
        travel(node.right, check)
    }
    const result = []
    const check = val => {
        if (!result.length || val > result[result.length - 1][1] + 1) {
			result.push([val, val])
		} else {
			result[result.length - 1][1] = val
        }
    }
    travel(this.tree, check)
    return result
};

/** 
 * Your SummaryRanges object will be instantiated and called as such:
 * var obj = new SummaryRanges()
 * obj.addNum(val)
 * var param_2 = obj.getIntervals()
 */
Data Stream as Disjoint Intervals