Data Stream as Disjoint Intervals

Design a class SummaryRanges that adds integers one by one and returns the disjoint sorted list of intervals they form.

Example 1

addNum(1)→[[1,1]], addNum(3)→[[1,1],[3,3]], addNum(7)→[[1,1],[3,3],[7,7]], addNum(2)→[[1,3],[7,7]], addNum(6)→[[1,3],[6,7]]

Solution Approach

Use a TreeMap. When adding a number, merge with any overlapping or adjacent intervals.

TreeMap: key=start, value=end.
On addNum(val): if already covered, skip.
Find floor and ceiling entries. Merge with floor if floor.end >= val-1. Merge with ceiling if ceil.start <= val+1.
Insert/update merged interval.

Java

import java.util.*;

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

    public void addNum(int val) {
        if (map.floorKey(val) != null && map.get(map.floorKey(val)) >= val) return;
        int start = val, end = val;
        Integer lo = map.floorKey(val), hi = map.ceilingKey(val);
        if (lo != null && map.get(lo) >= val - 1) { start = lo; end = Math.max(end, map.get(lo)); map.remove(lo); }
        if (hi != null && hi <= val + 1) { end = Math.max(end, map.get(hi)); map.remove(hi); }
        map.put(start, end);
    }

    public int[][] getIntervals() {
        int[][] res = new int[map.size()][2];
        int i = 0;
        for (Map.Entry<Integer,Integer> e : map.entrySet()) { res[i][0]=e.getKey(); res[i++][1]=e.getValue(); }
        return res;
    }
}

Time Complexity: addNum: O(log N), getIntervals: O(N)
Space Complexity: O(N)