Data Stream as Disjoint Intervals
Hard · Intervals · Binary Search · Design · Ordered Set
Problem
Non-negative integers arrive one at a time. At any moment you must be able to summarize everything seen so far as a sorted list of disjoint intervals, where runs of consecutive integers are merged: seeing 1, 3, 7, 2, 6 gives [1,3] and [6,7].
Implement SummaryRanges:
- SummaryRanges() starts with an empty stream.
- addNum(value) adds value to the stream. Values may repeat; a repeat changes nothing.
- getIntervals() returns the numbers seen so far as a list of closed intervals [start, end], sorted by start, with no two intervals overlapping or touching.
Tests replay a call sequence: the first entry names the class and its constructor arguments, each later entry is a method with its arguments, and calls returning nothing report None.
Examples
Input: ops = ["SummaryRanges","addNum","getIntervals","addNum","getIntervals","addNum","getIntervals","addNum","getIntervals"], args = [[],[1],[],[3],[],[7],[],[2],[]] Output: [None, None, [[1, 1]], None, [[1, 1], [3, 3]], None, [[1, 1], [3, 3], [7, 7]], None, [[1, 3], [7, 7]]]
Adding 2 fills the gap between [1,1] and [3,3], so they merge into [1,3].
Input: ops = ["SummaryRanges","addNum","addNum","addNum","getIntervals"], args = [[],[2],[2],[9],[]] Output: [None, None, None, None, [[2, 2], [9, 9]]]
The second 2 is already covered.
Input: ops = ["SummaryRanges","getIntervals","addNum","getIntervals"], args = [[],[],[0],[]] Output: [None, [], None, [[0, 0]]]
An empty stream has no intervals; 0 is a valid value.
Constraints
- 0 <= value <= 10^4
- at most 3 · 10^4 calls to addNum and getIntervals in total
- at most 100 calls to getIntervals
Approaches
- Baseline: store values, merge on every read — time addNum O(1), getIntervals O(n log n), space O(n)
Follow-up
With many more getIntervals calls than additions, keep the intervals as above. If additions dominate and the interval list is rarely read, storing raw values and merging on demand is cheaper per add. The use cases ask, after each addition, how many intervals there are and how long the longest one is.
Related problems
Start free on Cariara · Coding problems · System design studio
