352. Data Stream as Disjoint Intervals

Given a data stream input of non-negative integers a1, a2, ..., an, ..., summarize the numbers seen so far as a list of disjoint intervals.

For example, suppose the integers from the data stream are 1, 3, 7, 2, 6, ..., then the summary will be:

[1, 1]
[1, 1], [3, 3]
[1, 1], [3, 3], [7, 7]
[1, 3], [7, 7]
[1, 3], [6, 7]

Follow up:
What if there are lots of merges and the number of disjoint intervals are small compared to the data stream's size?

Solution:

Use TreeMap to maintain a sorted map, when we return the list, we can simply iterate the treemap to give us the sorted intervals.

I use two maps to track interval start and interval ends respectively, my solution is very easy to understand.

Skip any value has been processed.

Merge intervals if the start map contains val+1 or end map contains val-1. Remove excessive start and end in both maps.

 class SummaryRanges {  
   TreeMap<Integer,Integer> startToEnd;  
   HashMap<Integer,Integer> endToStart;  
   HashSet<Integer> processed;  
   /** Initialize your data structure here. */  
   public SummaryRanges() {  
     startToEnd=new TreeMap<Integer,Integer>();  
     endToStart=new HashMap<Integer,Integer>();  
     processed=new HashSet<Integer>();  
   }  
   public void addNum(int val) {  
     if(!processed.add(val)) return;  
     int newStart=val;  
     int newEnd=val;  
     if(startToEnd.containsKey(val+1)){  
       newEnd=startToEnd.get(val+1);  
       startToEnd.remove(val+1);  
     }  
     if(endToStart.containsKey(val-1)){  
       newStart=endToStart.get(val-1);  
       endToStart.remove(val-1);  
     }  
     startToEnd.put(newStart,newEnd);  
     endToStart.put(newEnd,newStart);  
   }  
   public List<Interval> getIntervals() {  
     List<Interval> res=new ArrayList<Interval>();  
     for(Map.Entry<Integer,Integer> pairs : startToEnd.entrySet()){  
       Interval item=new Interval(pairs.getKey(),pairs.getValue());  
       res.add(item);  
     }  
     return res;  
   }  
 }