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 integer value to 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 by starti.
fromsortedcontainersimportSortedDictclassSummaryRanges:def__init__(self):self.mp=SortedDict()defaddNum(self,val:int)->None:n=len(self.mp)ridx=self.mp.bisect_right(val)lidx=nifridx==0elseridx-1keys=self.mp.keys()values=self.mp.values()if(lidx!=nandridx!=nandvalues[lidx][1]+1==valandvalues[ridx][0]-1==val):self.mp[keys[lidx]][1]=self.mp[keys[ridx]][1]self.mp.pop(keys[ridx])eliflidx!=nandval<=values[lidx][1]+1:self.mp[keys[lidx]][1]=max(val,self.mp[keys[lidx]][1])elifridx!=nandval>=values[ridx][0]-1:self.mp[keys[ridx]][0]=min(val,self.mp[keys[ridx]][0])else:self.mp[val]=[val,val]defgetIntervals(self)->List[List[int]]:returnlist(self.mp.values())# # Your SummaryRanges object will be instantiated and called as such:# # obj = SummaryRanges()# # obj.addNum(val)# # param_2 = obj.getIntervals()
classSummaryRanges{privateTreeMap<Integer,int[]>mp;publicSummaryRanges(){mp=newTreeMap<>();}publicvoidaddNum(intval){Integerl=mp.floorKey(val);Integerr=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);}elseif(l!=null&&val<=mp.get(l)[1]+1){mp.get(l)[1]=Math.max(val,mp.get(l)[1]);}elseif(r!=null&&val>=mp.get(r)[0]-1){mp.get(r)[0]=Math.min(val,mp.get(r)[0]);}else{mp.put(val,newint[]{val,val});}}publicint[][]getIntervals(){int[][]res=newint[mp.size()][2];inti=0;for(int[]range:mp.values()){res[i++]=range;}returnres;}}/** * Your SummaryRanges object will be instantiated and called as such: * SummaryRanges obj = new SummaryRanges(); * obj.addNum(val); * int[][] param_2 = obj.getIntervals(); */
classSummaryRanges{private:map<int,vector<int>>mp;public:SummaryRanges(){}voidaddNum(intval){autor=mp.upper_bound(val);autol=r==mp.begin()?mp.end():prev(r);if(l!=mp.end()&&r!=mp.end()&&l->second[1]+1==val&&r->second[0]-1==val){l->second[1]=r->second[1];mp.erase(r);}elseif(l!=mp.end()&&val<=l->second[1]+1)l->second[1]=max(val,l->second[1]);elseif(r!=mp.end()&&val>=r->second[0]-1)r->second[0]=min(val,r->second[0]);elsemp[val]={val,val};}vector<vector<int>>getIntervals(){vector<vector<int>>res;for(auto&range:mp)res.push_back(range.second);returnres;}};/** * Your SummaryRanges object will be instantiated and called as such: * SummaryRanges* obj = new SummaryRanges(); * obj->addNum(val); * vector<vector<int>> param_2 = obj->getIntervals(); */