Data Stream as Disjoint Intervals

hard intervals tree map design

Problem

Design a data structure that summarizes a stream of integers as a sorted list of disjoint intervals.

InputaddNum(1); addNum(3); addNum(7); addNum(2); addNum(6)

Output[[1,3],[6,7]]

Final intervals after merges and insertions: [1,3] and [6,7].

stream (comma-separated)

import bisect
class SummaryRanges:
    def __init__(self):
        self.iv = []  # list of [l, r]
    def addNum(self, v):
        starts = [i[0] for i in self.iv]
        i = bisect.bisect_left(starts, v)
        if i > 0 and self.iv[i-1][1] >= v: return
        merge_l = i > 0 and self.iv[i-1][1] + 1 == v
        merge_r = i < len(self.iv) and self.iv[i][0] - 1 == v
        if merge_l and merge_r:
            self.iv[i-1][1] = self.iv[i][1]; self.iv.pop(i)
        elif merge_l:
            self.iv[i-1][1] = v
        elif merge_r:
            self.iv[i][0] = v
        else:
            self.iv.insert(i, [v, v])
    def getIntervals(self):
        return self.iv[:]

class SummaryRanges {
  constructor() { this.iv = []; }
  addNum(v) {
    let lo = 0, hi = this.iv.length;
    while (lo < hi) { const m = (lo + hi) >> 1; this.iv[m][0] < v ? lo = m + 1 : hi = m; }
    if (lo > 0 && this.iv[lo - 1][1] >= v) return;
    const ml = lo > 0 && this.iv[lo - 1][1] + 1 === v;
    const mr = lo < this.iv.length && this.iv[lo][0] - 1 === v;
    if (ml && mr) { this.iv[lo - 1][1] = this.iv[lo][1]; this.iv.splice(lo, 1); }
    else if (ml) this.iv[lo - 1][1] = v;
    else if (mr) this.iv[lo][0] = v;
    else this.iv.splice(lo, 0, [v, v]);
  }
  getIntervals() { return this.iv.slice(); }
}

class SummaryRanges {
    TreeMap iv = new TreeMap<>();
    public void addNum(int v) {
        Map.Entry l = iv.floorEntry(v);
        Map.Entry r = iv.ceilingEntry(v);
        if (l != null && l.getValue()[1] >= v) return;
        boolean ml = l != null && l.getValue()[1] + 1 == v;
        boolean mr = r != null && r.getValue()[0] - 1 == v;
        if (ml && mr) { l.getValue()[1] = r.getValue()[1]; iv.remove(r.getKey()); }
        else if (ml) l.getValue()[1] = v;
        else if (mr) { iv.remove(r.getKey()); iv.put(v, new int[]{v, r.getValue()[1]}); }
        else iv.put(v, new int[]{v, v});
    }
    public int[][] getIntervals() {
        int[][] out = new int[iv.size()][];
        int k = 0;
        for (int[] x : iv.values()) out[k++] = x;
        return out;
    }
}

class SummaryRanges {
    map iv;  // start -> end
public:
    void addNum(int v) {
        auto r = iv.lower_bound(v);
        auto l = (r == iv.begin()) ? iv.end() : prev(r);
        if (l != iv.end() && l->second >= v) return;
        bool ml = l != iv.end() && l->second + 1 == v;
        bool mr = r != iv.end() && r->first - 1 == v;
        if (ml && mr) { l->second = r->second; iv.erase(r); }
        else if (ml) l->second = v;
        else if (mr) { int e = r->second; iv.erase(r); iv[v] = e; }
        else iv[v] = v;
    }
    vector> getIntervals() {
        vector> out;
        for (auto& [s, e] : iv) out.push_back({s, e});
        return out;
    }
};

Explanation

We keep the summary as a sorted list of disjoint intervals iv. When a new number arrives, we only need to look at its immediate left and right neighbors to decide what changes.

A binary search finds the slot i where the new value v belongs. If the interval just before it already covers v (its end is >= v), the number is a duplicate and we do nothing.

Otherwise we check two touch conditions: merge_l means the left interval ends exactly at v - 1, and merge_r means the right interval starts exactly at v + 1. If both touch, v bridges them into one interval; if only one touches, we extend that interval by one; if neither touches, we insert [v, v] as a brand-new singleton.

Example: adding 1, 3, 7, 2, 6. The 2 bridges [1,1] and [3,3] into [1,3], and the 6 bridges with 7 into [6,7], giving [[1,3],[6,7]].

Because we only ever inspect two neighbors and use a sorted structure, each insert is quick even with many numbers.

Time: O(log n) per add Space: O(n)