Data Stream as Disjoint Intervals

Implement SummaryRanges to summarize the distinct nonnegative integers seen in a stream.

• SummaryRanges() starts with no values.
• addNum(value) adds a value. Adding a value already present does not change the summary.
• getIntervals() returns the maximal inclusive intervals covering exactly the values seen so far, sorted by their starting values.

Consecutive values belong to the same interval. For example, the values 2, 3, 4, 8 are summarized as [[2,4],[8,8]]. With no values, return an empty array.

Follow-up: How would you handle a stream with many merges when the number of disjoint intervals stays small?

Example 1:

Input: ["SummaryRanges","addNum","addNum","getIntervals","addNum","getIntervals"]
[[],[2],[4],[],[3],[]]

Output: [null,null,null,[[2,2],[4,4]],null,[[2,4]]]

Explanation: After adding 2 and 4, the summary is [[2,2],[4,4]]. Adding 3 fills the gap, joining both intervals into [[2,4]].

Example 2:

Input: ["SummaryRanges","getIntervals","addNum","addNum","getIntervals"]
[[],[],[0],[0],[]]

Output: [null,[],null,null,[[0,0]]]

Explanation: An empty stream has no intervals. Adding 0 twice still represents the single value 0, so the final summary is [[0,0]].

Example 3:

Input: ["SummaryRanges","addNum","addNum","addNum","getIntervals"]
[[],[8],[6],[7],[]]

Output: [null,null,null,null,[[6,8]]]

Explanation: The values arrive in the order 8, 6, 7. Together they form the consecutive range from 6 through 8, so the summary is [[6,8]].

Constraints:

• 0 <= value <= 10000
• At most 30000 calls are made to addNum and getIntervals combined.
• At most 100 calls are made to getIntervals.