Integers arrive one at a time. At any moment you must be able to report the set of numbers seen so far as a sorted list of disjoint, maximal closed intervals.
Implement SummaryRanges:
add_num(value): addvalueto the stream (it may be a repeat).get_intervals(): return a list of[start, end]pairs, sorted by start, covering exactly the distinct values seen, with no two intervals overlapping or adjacent (adjacent runs like[1, 2]and[3, 3]must be merged into[1, 3]).
sr = SummaryRanges()
sr.add_num(4); sr.get_intervals() # [[4, 4]]
sr.add_num(8); sr.get_intervals() # [[4, 4], [8, 8]]
sr.add_num(6); sr.get_intervals() # [[4, 4], [6, 6], [8, 8]]
sr.add_num(5); sr.get_intervals() # [[4, 6], [8, 8]]
sr.add_num(7); sr.get_intervals() # [[4, 8]]
Constraints: 0 <= value <= 2 * 10**9 (fits in a signed 32-bit int); tens of thousands of calls, with get_intervals possibly called after every add. Rebuilding the intervals from all values seen on every call is too slow; aim for O(log n) work per add_num, plus the size of the output for get_intervals.
Show hint
keep the current intervals themselves, ordered by start. A new value can only touch the interval just before it and the one just after it, so find those two and merge.