Given a data stream input of non-negative integers a1, a2, ..., an
, summarize the numbers seen so far as a list of disjoint intervals.
Implement the SummaryRanges
class:
-
SummaryRanges()
Initializes the object with an empty stream. -
void addNum(int val)
Adds the integerval
to the stream. -
int[][] getIntervals()
Returns a summary of the integers in the stream currently as a list of disjoint intervals[starti, endi]
.
Example 1:
Input
["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"]
[[], [1], [], [3], [], [7], [], [2], [], [6], []]
Output
[null, null, [[1, 1]], null, [[1, 1], [3, 3]], null, [[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, [[1, 3], [6, 7]]]
Explanation
SummaryRanges summaryRanges = new SummaryRanges();
summaryRanges.addNum(1); // arr = [1]
summaryRanges.getIntervals(); // return [[1, 1]]
summaryRanges.addNum(3); // arr = [1, 3]
summaryRanges.getIntervals(); // return [[1, 1], [3, 3]]
summaryRanges.addNum(7); // arr = [1, 3, 7]
summaryRanges.getIntervals(); // return [[1, 1], [3, 3], [7, 7]]
summaryRanges.addNum(2); // arr = [1, 2, 3, 7]
summaryRanges.getIntervals(); // return [[1, 3], [7, 7]]
summaryRanges.addNum(6); // arr = [1, 2, 3, 6, 7]
summaryRanges.getIntervals(); // return [[1, 3], [6, 7]]
Constraints:
-
0 <= val <= 104
- At most
3 * 104
calls will be made toaddNum
andgetIntervals
.
Follow up: What if there are lots of merges and the number of disjoint intervals is small compared to the size of the data stream?
SOLUTION:
import bisect
class SummaryRanges:
def __init__(self):
self.nums = []
self.dup = set()
def addNum(self, val: int) -> None:
if val not in self.dup:
bisect.insort(self.nums, val)
self.dup.add(val)
def getIntervals(self) -> List[List[int]]:
nums = self.nums
n = len(nums)
if n == 0:
return []
ranges = [[nums[0]]]
for i in range(1, n):
if nums[i] == ranges[-1][-1] or nums[i] == ranges[-1][-1] + 1:
ranges[-1].append(nums[i])
else:
ranges.append([nums[i]])
return [[r[0], r[-1]] for r in ranges]
# Your SummaryRanges object will be instantiated and called as such:
# obj = SummaryRanges()
# obj.addNum(val)
# param_2 = obj.getIntervals()
Top comments (0)