Statement▼
You are given a stream of non-negative integers
Your task is to implement the Summary Ranges class, where:
Constructor: Initializes the Summary Ranges object with an empty stream.
Add Num(int value): Adds the integer
valueto the stream.Get Intervals(): Returns the current summary of numbers as a list of disjoint intervals
[start_i, end_i], sorted bystart_i.
Note: Each number belongs to exactly one interval. Intervals must merge whenever new numbers connect or extend existing ones, and duplicate insertions should not affect the summary.
Constraints:
0≤ value≤104 At most
3×104 calls will be made to Add Num() and Get Intervals().At most
102 calls will be made to Get Intervals().
Solution
When numbers arrive one after another in a stream, it’s easy to imagine them as scattered pebbles landing on a number line. If we keep them as-is, the picture quickly becomes messy. Instead, we want to summarize what we’ve seen into clean stretches of consecutive values, i.e., intervals. The challenge is that every new number can behave differently:
It may fall inside an existing interval.
It may extend an interval by one.
It may even act like a missing puzzle piece that connects two intervals into one larger block.
This constant merging and organizing is why the “intervals” pattern is the right fit. Rather than storing every number, we maintain only the boundaries of disjoint intervals and carefully update them when new values arrive. This way, our summary stays compact, sorted, and easy to return.
We start by keeping a sorted collection of intervals instead of recording every number one by one. Each new value starts as a small single-point interval, and then we look at the ranges around it to decide how it fits.
If an existing range already covers the value, we simply ignore it.
If the value lies just beyond the end of a range, we extend that range to include it.
If the value lies just before the start of a range, we merge it with that range.
If the value sits exactly between two ranges, we merge them into one larger range.