问题描述：
Given a data stream input of non-negative integers a1, a2, …, an, …, summarize the numbers seen so far as a list of disjoint intervals.
解题思路：
这道题是目前最新的题，其实思路很容易找到，难点在于考虑到所有的可能的情形。
首先要确定类必须有一个保存当前结果的集合类List<Interval>，其元素的按Interval的起始值的大小排序，当调用getIntervals()时直接返回该lists，当调用addNum(val)类时会对List<Interval>中的类进行调整。具体调整步骤如下：
1）调用自定义的findIndex(int val)方法找到Interval起始值小于val的最大的Interval的值。具体查找过程可以用二分查找的方法。这里需要考虑两个特殊情况：val值比位置为0的Interval的起始值还小；或者比最后一个Interval的起始值还大。这两个情况可以做特殊处理（分别返回-1，和lists.size()-1）。
2）针对返回值考虑如下情况(直接举具体的例子，相信大家都可以理解)：
若返回值是-1：
a.若当前值为1，位置为0的Interval值为(2,x),可以修改这个Interval为（1，x）；
b.若当前值为1，位置为0的Interval值为（3，x）,可以新建一个Interval(1,1),加入lists中。
若返回值是lists.size()-1:
a.若当前值为11，最后一个Interval是（8,11），不做修改；
b.若当前值为11，最后一个Intever是（8,10），需要将它改为（8,11）；
c.若当前值为11，最后一个Intever是（8,9），需要新建一个（11,11），加入lists中。
若返回值pos在[0,lists.size()-1);
a.如果val==lists.get(pos+1).start-1 && val==lists.get(pos).end+1：需要将两个Interval合并成一个新的Interval；
b.如果val==lists.get(pos+1).start-1 && val！=lists.get(pos).end+1:需要修改lists[pos+1]的值;
c.如果val!=lists.get(pos+1).start-1 && val==lists.get(pos).end+1需要修改lists[pos]的值;
d.其他情况:新建一个Interval：（val,val）并加入到lists中。具体代码：
public class SummaryRanges { List<Interval> lists;
/** Initialize your data structure here. */
public SummaryRanges() {
lists=new ArrayList<Interval>(); } public void addNum(int val) {
if(lists.size()==0){
Interval p = new Interval(val,val);
lists.add(p);
return;
}
if(lists.size()==1){
if(lists.get(0).end <val){
Interval p=lists.remove(0);
if(p.end==val-1){
Interval p1=new Interval(p.start,val);
lists.add(p1);
return;
}
Interval p1=new Interval(val,val);
lists.add(p);
lists.add(p1); return;
}
else if(lists.get(0).start >val){
Interval p=lists.remove(0);
if(p.start==val+1){
Interval p1=new Interval(val,p.start);
lists.add(p1); return;
}
Interval p1=new Interval(val,val);
lists.add(p1);
lists.add(p); return;
}
else{
return;
}
}
int pos=findIndex(val);
if(pos==-1){
if(val==lists.get(0).start-1){
lists.get(0).start=val;
return;
}
else{
Interval p1=new Interval(val,val);
lists.add(0, p1);
return;
}
}
if(pos==lists.size()-1){
if(val<=lists.get(pos).end){
return;
}
else{
if(val==lists.get(pos).end+1){
lists.get(pos).end=val;
return;
}
else{
Interval p1=new Interval(val,val);
lists.add(p1); return;
}
}
} if(val<=lists.get(pos).end){
return;
}
else if(val==lists.get(pos+1).start-1 && val==lists.get(pos).end+1){
Interval p1=lists.remove(pos);
Interval p2=lists.remove(pos);
Interval p=new Interval(p1.start, p2.end); lists.add(pos, p);
return;
}
else if(val==lists.get(pos+1).start-1){
lists.get(pos+1).start=val;
return;
}
else if(val==lists.get(pos).end+1){
lists.get(pos).end=val;
return;
}
else{
Interval p=new Interval(val, val);
lists.add(pos+1, p); return;
} } public List<Interval> getIntervals() {
return lists;
} private int findIndex(int val){
int start=0;
int end=lists.size()-1;
if(lists.get(0).start>val)
return -1;
if(lists.get(lists.size()-1).start<val)
return lists.size()-1;
while(start<end){
int mid=(start+end)/2;
if(val<lists.get(mid).start){
end=mid-1;
}
else if(val>lists.get(mid).start){
if(val<lists.get(mid+1).start)
return mid;
else
start= mid+1;
}
else
return mid;
}
return start;
}
}
步骤可能有些繁琐，以后有时间会继续优化代码。
