Data Stream as Disjoint Intervals

Question

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?

Analysis

We can use the start num of each Interval as a key to search for the interval where we are going to insert the new value.

Solution

public class SummaryRanges {
    List<Interval> rangeList;
    /** Initialize your data structure here. */
    public SummaryRanges() {
        rangeList=new LinkedList<Interval>();
    }

    public void addNum(int val) {
        if(rangeList.isEmpty()) rangeList.add(new Interval(val,val));
        else{
            int len=rangeList.size();
            int lo=0, hi=len-1;
            while(lo<hi){
                int mid=lo+(hi-lo)/2;
                Interval tmp=rangeList.get(mid);
                if(val>=tmp.start && val<=tmp.end) return;
                if(val<tmp.start) hi=mid;
                else              lo=mid+1;
            }
            Interval target=rangeList.get(lo);
            Interval targetLeft=(lo>=1)?rangeList.get(lo-1):null;
            if(val>=target.start && val<=target.end) return;

            if(val<target.start){
                if(targetLeft==null){
                    if(val+1==target.start) target.start=val;
                    else rangeList.add(0,new Interval(val,val));
                }else{
                    if(targetLeft.end+2==target.start) {
                        targetLeft.end=target.end; 
                        rangeList.remove(lo);
                    }else{
                        if(targetLeft.end+1==val) targetLeft.end=val;
                        else if(target.start-1==val) target.start=val;
                             else rangeList.add(lo,new Interval(val,val));
                    }
                }
            }else{
                if(target.end+1==val) target.end=val;
                else rangeList.add(new Interval(val,val));
            }
        }
    }

    public List<Interval> getIntervals() {
        return rangeList;
    }
}