# 352 Data Stream as Disjoint Intervals

data stream input皆為正整數，將input data stream用數字區間表示。

例如：data stream input=[1,3,7,2,6] 可以表示為：[1,3] [6,7]

提供資料結構如下

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class SummaryRanges {

    /** Initialize your data structure here. */
    public SummaryRanges() {

    }

    public void addNum(int val) {

    }

    public List<Interval> getIntervals() {

    }
}

/**
 * Your SummaryRanges object will be instantiated and called as such:
 * SummaryRanges obj = new SummaryRanges();
 * obj.addNum(val);
 * List<Interval> param_2 = obj.getIntervals();
 */

Idea 用list來存數字區間，getInterval()就return list。 addNum(): 將list用interval.start遞增排序，在list中找到第一個start比val大的數字區間，將index設在該位置。若前一個數字區間有合併的可能，則將index往前移一個位置。 用一while迴圈檢查index i的數字區間是否可以和val合併，若可以，更新start, end，並把該區間移除。 離開while迴圈後，將[start, end] 區間插入index i。

Code

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class SummaryRanges {
    List<Interval> list;
    /** Initialize your data structure here. */
    public SummaryRanges() {
        list = new ArrayList<>();
    }

    public void addNum(int val){
        Collections.sort(list, new Comparator<Interval>() {
            @Override
            public int compare(Interval a, Interval b) {
                return a.start < b.start ? -1 : 1;
            }
        });

        int start = val, end = val;
        int i=0;
        if(list.size() > 0){
            Interval cur = list.get(0);
            while(val > cur.start && ++i < list.size()){
                cur = list.get(i);
            }
            if(i != 0 && list.get(i-1).end+1 >= val) i--;
        }

        while(i < list.size() && val+1 >= list.get(i).start && val-1 <= list.get(i).end){
            start = Math.min(start, list.get(i).start);
            end = Math.max(end, list.get(i).end);
            list.remove(i);
        }

        if(i >= list.size()){
            list.add(new Interval(start,end));
        }else{
            list.add(i, new Interval(start,end));
        }

    }  

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

/**
 * Your SummaryRanges object will be instantiated and called as such:
 * SummaryRanges obj = new SummaryRanges();
 * obj.addNum(val);
 * List<Interval> param_2 = obj.getIntervals();
 */

Followup Q: What if there are lots of merges and the number of disjoint intervals are small compared to the data stream's size? A: 用list存時，搜尋區間的時間複雜度為O(N)，若改用binary search tree存，可以減少到O(logN)