## Data Stream as Disjoint Intervals

• Time:O(n\log n)
• Space:O(n)

## C++

``````class SummaryRanges {
public:
if (map.count(val))
return;

const int lo = lowerKey(val);
const int hi = higherKey(val);

// {lo, map[lo][1]} + val + {hi, map[hi][1]} = {lo, map[hi][1]}
if (lo >= 0 && hi >= 0 && map[lo][1] + 1 == val && val + 1 == hi) {
map[lo][1] = map[hi][1];
map.erase(hi);
// {lo, map[lo][1]} + val = {lo, val}
} else if (lo >= 0 && map[lo][1] + 1 >= val) {
map[lo][1] = max(map[lo][1], val);
} else if (hi >= 0 && val + 1 == hi) {
// val + {hi, map[hi][1]} = {val, map[hi][1]}
map[val] = {val, map[hi][1]};
map.erase(hi);
} else {
map[val] = {val, val};
}
}

vector<vector<int>> getIntervals() {
vector<vector<int>> intervals;
for (const auto& [_, interval] : map)
intervals.push_back(interval);
return intervals;
}

private:
map<int, vector<int>> map;  // {start: {start, end}}

// maximum in map < key
int lowerKey(int key) {
auto it = map.lower_bound(key);  // minimum in map >= key
if (it == begin(map))
return -1;
return (--it)->first;
}

// minimum in map > key
int higherKey(int key) {
const auto it = map.upper_bound(key);  // minimum in map > key
if (it == cend(map))
return -1;
return it->first;
}
};
``````

## JAVA

``````class SummaryRanges {
if (map.containsKey(val))
return;

final Integer lo = map.lowerKey(val);  // maximum in map < key
final Integer hi = map.higherKey(val); // minimum in map > key

// {lo, map.get(lo)[1]} + val + {hi, map.get(hi)[1]} = {lo, map.get(hi)[1]}
if (lo != null && hi != null && map.get(lo)[1] + 1 == val && val + 1 == hi) {
map.get(lo)[1] = map.get(hi)[1];
map.remove(hi);
// {lo, map.get(lo)[1]} + val = {lo, val}
} else if (lo != null && map.get(lo)[1] + 1 >= val) {
map.get(lo)[1] = Math.max(map.get(lo)[1], val);
// val + {hi, map.get(hi)[1]} = {val, map.get(hi)[1]}
} else if (hi != null && val + 1 == hi) {
map.put(val, new int[] {val, map.get(hi)[1]});
map.remove(hi);
} else {
map.put(val, new int[] {val, val});
}
}

public int[][] getIntervals() {
List<int[]> intervals = new ArrayList<>(map.values());
return intervals.toArray(new int[intervals.size()][]);
}

// {start: {start, end}}
private TreeMap<Integer, int[]> map = new TreeMap<>();
}
``````