Sponsored
Sponsored
In this approach, maintain a sorted array of intervals and merge them appropriately as new numbers are added. When adding a new number, iterate through the intervals to find the potential merging points and update the intervals accordingly.
Time Complexity: O(N), where N is the number of intervals (after all numbers are added).
Space Complexity: O(N)
1class SummaryRanges:
2 def __init__(self):
3 self.intervals = []
4
5 def addNum(self, value: int) -> None:
6 for interval in self.intervals:
7 if interval[0] <= value <= interval[1]:
8 return
9 if interval[0] == value + 1:
10 interval[0] = value
11 self._merge()
12 return
13 if interval[1] == value - 1:
14 interval[1] = value
15 self._merge()
16 return
17 self.intervals.append([value, value])
18 self.intervals.sort()
19
20 def getIntervals(self) -> list:
21 return self.intervals
22
23 def _merge(self):
24 merged = []
25 for interval in self.intervals:
26 if not merged or merged[-1][1] < interval[0] - 1:
27 merged.append(interval)
28 else:
29 merged[-1][1] = max(merged[-1][1], interval[1])
30 self.intervals = merged
31This Python solution maintains a list of intervals and updates it as new numbers are added. Each number is checked against existing intervals for possible merges.
This approach uses a data structure like TreeMap in Java or SortedDict in Python to maintain the intervals in sorted order. This provides efficient query and update operations which is essential for managing intervals dynamically.
Time Complexity: O(log N) for add, where N is the number of intervals.
Space Complexity: O(N)
1import java.util.TreeMap;
2
3
The Java solution uses a TreeMap to efficiently maintain and update intervals. Each time a number is added, it checks for possible merges with adjacent intervals and updates the map accordingly.