Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/352.html
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 value)Adds the integervalueto the stream.int[][] getIntervals()Returns a summary of the integers in the stream currently as a list of disjoint intervals[starti, endi]. The answer should be sorted bystarti.
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 <= value <= 104- At most
3 * 104calls will be made toaddNumandgetIntervals. - At most
102calls will be made togetIntervals.
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?
Algorithm
Use TreeMap
To get previous range last index, and next range first index. Then compare and decide if merge or not.
Integer l = tree.lowerKey(val); // @note: Returns the greatest key strictly less than the given key
Integer h = tree.higherKey(val); // @note: Returns the least key strictly greater than the given key
Interval start/end check
Every time a new number val comes in, a new interval [val, val] is generated, and an empty interval array res is created, and a variable cur is used to store the position of the new interval.
Traverse the existing interval array intervals, for each traversed current interval interval,
- If the end position of the interval to be added plus 1 is smaller than the start position of the current interval, indicating that the two are not connected, add the current interval to res.
- Otherwise, when the start position of the interval to be added is greater than the end position of the current position plus 1, it means that there is no intersection between the two, and the current interval can be added to
res,- But at this time, cur should be incremented by 1 because the position to be added to the interval is behind the current interval.
- Otherwise, the two will overlap and need to be merged,
- At this time, use the smaller of the two starting positions to update the starting position of the interval to be added,
- In the same way, use the larger of the two end positions to update the end position of the interval to be added.
Finally, the interval to be added is placed at the cur position in res, and then res is assigned to intervals
Follow up: What if there are lots of merges and the number of disjoint intervals are small compared to the data stream’s size?
- lots of merges
->add() cannot be too costy - the number of disjoint intervals are small
->get() can be costy
to reduce cost of add(), use O(logn) for insertion of points (no merge), and maintain order
get will have to calculate the disjoint intervals on the fly (basically lazy loading, do a merge on get() trigger)
Code
-
import java.util.*; public class Data_Stream_as_Disjoint_Intervals { public static void main(String[] args) { Data_Stream_as_Disjoint_Intervals out = new Data_Stream_as_Disjoint_Intervals(); SummaryRanges s = out.new SummaryRanges(); // // ["SummaryRanges","addNum","getIntervals","addNum","getIntervals","addNum","getIntervals", // "addNum","getIntervals","addNum","getIntervals"] // [[],[1],[],[3],[],[7],[],[2],[],[6],[]] // s.addNum(1); // s.addNum(3); // s.addNum(7); // s.addNum(2); //// s.intervals.stream().forEach(i -> System.out.println(Arrays.toString(i))); // s.addNum(6); // s.intervals.stream().forEach(i -> System.out.println(Arrays.toString(i))); s.addNum(49); s.addNum(97); s.addNum(53); s.addNum(5); s.addNum(33); s.addNum(65); s.addNum(62); // s.intervals.stream().forEach(i -> System.out.println(Arrays.toString(i))); int[][] r = s.getIntervals(); System.out.println(Arrays.toString(s.getIntervals())); } public class SummaryRanges_TreeMap { // val to interval TreeMap<Integer, Interval> tree; public SummaryRanges_TreeMap() { tree = new TreeMap<>(); } public void addNum(int val) { if(tree.containsKey(val)) { return; } Integer l = tree.lowerKey(val); // @note: Returns the greatest key strictly less than the given key, Integer h = tree.higherKey(val); // @note: Returns the least key strictly greater than the given key if(l != null && h != null && tree.get(l).end + 1 == val && val + 1 == h) { tree.get(l).end = tree.get(h).end; tree.remove(h); } else if(l != null && tree.get(l).end + 1 >= val) { tree.get(l).end = Math.max(tree.get(l).end, val); } else if(h != null && h == val + 1) { tree.put(val, new Interval(val, tree.get(h).end)); tree.remove(h); } else { tree.put(val, new Interval(val, val)); } } public List<Interval> getIntervals() { return new ArrayList<>(tree.values()); } } class SummaryRanges { PriorityQueue<int[]> intervals; List<int[]> resultTmp = new ArrayList<>(); /** Initialize your data structure here. */ public SummaryRanges() { intervals = new PriorityQueue<>(new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) { return o1[0] - o2[0]; } }); } public void addNum(int val) { int[] newInterval = new int[]{val, val}; List<int[]> result = new ArrayList<>(); int newIntervalIndex = 0; for (int[] interval : resultTmp) { if (newInterval[1] + 1 < interval[0]) { result.add(newIntervalIndex, interval); // ++newIntervalIndex; // @note: right newIntervalIndex to insert } else if (newInterval[0] > interval[1] + 1) { result.add(newIntervalIndex, interval); ++newIntervalIndex; } else { newInterval[0] = Math.min(newInterval[0], interval[0]); newInterval[1] = Math.max(newInterval[1], interval[1]); // result.add(newIntervalIndex, newInterval); // ++resultPonter; } } result.add(newIntervalIndex, newInterval); resultTmp = result; intervals.clear(); resultTmp.forEach(intervals::offer); } public int[][] getIntervals() { return intervals.toArray(new int[intervals.size()][]); // @note } } /** * Your SummaryRanges object will be instantiated and called as such: * SummaryRanges obj = new SummaryRanges(); * obj.addNum(val); * int[][] param_2 = obj.getIntervals(); */ } ############ class SummaryRanges { private TreeMap<Integer, int[]> mp; public SummaryRanges() { mp = new TreeMap<>(); } public void addNum(int val) { Integer l = mp.floorKey(val); Integer r = mp.ceilingKey(val); if (l != null && r != null && mp.get(l)[1] + 1 == val && mp.get(r)[0] - 1 == val) { mp.get(l)[1] = mp.get(r)[1]; mp.remove(r); } else if (l != null && val <= mp.get(l)[1] + 1) { mp.get(l)[1] = Math.max(val, mp.get(l)[1]); } else if (r != null && val >= mp.get(r)[0] - 1) { mp.get(r)[0] = Math.min(val, mp.get(r)[0]); } else { mp.put(val, new int[] {val, val}); } } public int[][] getIntervals() { int[][] res = new int[mp.size()][2]; int i = 0; for (int[] range : mp.values()) { res[i++] = range; } return res; } } /** * Your SummaryRanges object will be instantiated and called as such: * SummaryRanges obj = new SummaryRanges(); * obj.addNum(val); * int[][] param_2 = obj.getIntervals(); */ -
class SummaryRanges { public: SummaryRanges() {} void addNum(int val) { vector<int> newInterval{val, val}; int i = 0, overlap = 0, n = intervals.size(); for (; i < n; ++i) { if (newInterval[1] + 1 < intervals[i][0]) break; if (newInterval[0] <= intervals[i][1] + 1) { newInterval[0] = min(newInterval[0], intervals[i][0]); newInterval[1] = max(newInterval[1], intervals[i][1]); ++overlap; } } if (overlap > 0) { intervals.erase(intervals.begin() + i - overlap, intervals.begin() + i); } intervals.insert(intervals.begin() + i - overlap, newInterval); } vector<vector<int>> getIntervals() { return intervals; } private: vector<vector<int>> intervals; }; -
# Definition for an interval. # class Interval(object): # def __init__(self, s=0, e=0): # self.start = s # self.end = e class SummaryRanges: def __init__(self): self.intervals = [] def insert(self, newInterval: List[int]): """ :type intervals: List[Interval] :type newInterval: Interval :rtype: List[Interval] """ intervals = self.intervals # print intervals if not intervals: intervals.append(newInterval) return s, e = newInterval[0], newInterval[1] left = list(filter(lambda x: x[1] < newInterval[0], intervals)) right = list(filter(lambda x: x[0] > newInterval[1], intervals)) # print left, right, (s, e) if left + right != intervals: s = min(intervals[len(left)][0], s) e = max(intervals[~len(right)][1], e) newIntv = [s, e] if left and left[-1][1] + 1 == s: newIntv[0] = left[-1][0] left = left[:-1] # cut out last one, which is merged with newIntv if right and right[0][0] - 1 == e: newIntv[1] = right[0][1] right = right[1:] # cut out first one, which is merged with newIntv self.intervals = left + [newIntv] + right def addNum(self, val: int) -> None: self.insert([val, val]) def getIntervals(self) -> List[List[int]]: return self.intervals # Your SummaryRanges object will be instantiated and called as such: # obj = SummaryRanges() # obj.addNum(val) # param_2 = obj.getIntervals() ############ class SummaryRanges: # better and easier, manual filter() via while def __init__(self): self.intervals = [] def addNum(self, val: int) -> None: new_interval = [val, val] merged_intervals = [] i = 0 # before overlap part while i < len(self.intervals) and self.intervals[i][1] < val - 1: merged_intervals.append(self.intervals[i]) i += 1 # process overlap while i < len(self.intervals) and self.intervals[i][0] <= val + 1: new_interval[0] = min(new_interval[0], self.intervals[i][0]) new_interval[1] = max(new_interval[1], self.intervals[i][1]) i += 1 merged_intervals.append(new_interval) # after overlap part while i < len(self.intervals): merged_intervals.append(self.intervals[i]) i += 1 self.intervals = merged_intervals def getIntervals(self) -> List[List[int]]: return self.intervals ############ ''' >>> mp = SortedDict() >>> mp.bisect_right(3) 0 >>> mp = SortedDict() >>> mp[1]=[1,1] >>> mp[3]=[3,3] >>> mp[5]=[5,5] >>> >>> mp SortedDict({1: [1, 1], 3: [3, 3], 5: [5, 5]}) >>> mp.bisect_right(-10) 0 >>> mp.bisect_right(100) 3 >>> mp.bisect_right(2) 1 >>> mp.values() SortedValuesView(SortedDict({1: [1, 1], 3: [3, 3], 5: [5, 5]})) >>> list(mp.values()) [[1, 1], [3, 3], [5, 5]] >>> ''' from sortedcontainers import SortedDict class SummaryRanges: def __init__(self): self.mp = SortedDict() def addNum(self, val: int) -> None: n = len(self.mp) ridx = self.mp.bisect_right(val) lidx = n if ridx == 0 else (ridx - 1) # n is similar to java treemap returning null keys = self.mp.keys() values = self.mp.values() if ( lidx != n and ridx != n and values[lidx][1] + 1 == val and values[ridx][0] - 1 == val ): self.mp[keys[lidx]][1] = self.mp[keys[ridx]][1] self.mp.pop(keys[ridx]) elif lidx != n and val <= values[lidx][1] + 1: # <= because, it could be [1 -> 10], and new add is [5,5] self.mp[keys[lidx]][1] = max(val, self.mp[keys[lidx]][1]) elif ridx != n and val >= values[ridx][0] - 1: self.mp[keys[ridx]][0] = min(val, self.mp[keys[ridx]][0]) else: self.mp[val] = [val, val] def getIntervals(self) -> List[List[int]]: return list(self.mp.values()) # # Your SummaryRanges object will be instantiated and called as such: # # obj = SummaryRanges() # # obj.addNum(val) # # param_2 = obj.getIntervals()