hardIntervalsPure DSA~45 min
Summarize a Number Stream as Disjoint Ranges
Integers arrive one at a time on a stream. At any moment the monitor must summarize everything seen as a minimal sorted list of disjoint, merged ranges.
Problem
Implement a structure with addNum(value) to record an integer and getIntervals() to return the seen numbers as a sorted list of disjoint inclusive intervals [start, end], merged so that consecutive integers collapse into one interval. Duplicate values have no effect.
Input
A sequence of addNum(value) and getIntervals() calls.
Output
Each getIntervals() returns the current minimal sorted list of disjoint [start, end] pairs.
Constraints
- 0 <= value <= 10^4 per addNum
- At most 3 * 10^4 addNum and getIntervals calls combined.
- Intervals are inclusive and must be maximally merged.
Examples
Example 1
Input
addNum(1), addNum(3), getIntervals(), addNum(7), addNum(2), getIntervals(), addNum(6), getIntervals()
Output
[[1,1],[3,3]]; [[1,3],[7,7]]; [[1,3],[6,7]]
Adding 2 bridges 1 and 3 into [1,3]; adding 6 extends 7 into [6,7].
Example 2
Input
addNum(5), addNum(5), getIntervals()
Output
[[5,5]]
Duplicate 5 leaves a single point interval.