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?

Time limit exceeded. since it is O(n) complexity. since fast set is O(1), fast get is O(n).

TreeSet

/**
 * 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; }
 * }
 */
public class SummaryRanges {
    Set<Integer> set = new TreeSet<>();
    /** Initialize your data structure here. */
    public SummaryRanges() {

    }
    //whether fast add or fast get
    public void addNum(int val) {
        set.add(val);
    }

    public List<Interval> getIntervals() {
        List<Interval> list = new ArrayList<>();
        Set<Integer> checked =new HashSet<>();
        for(Integer i : set){
            if(checked.contains(i)) continue;
            Interval interval = new Interval(i,i);
            checked.add(i);
            int l = i-1;
            while(set.contains(l)){
                interval.start--;
                checked.add(l--);
            }
            int r = i+1;
            while(set.contains(r) ) {
                interval.end++;
                checked.add(r++);
            }
            list.add(interval);
        }
        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();
 */

use fast get, O(lgN) set, use the property of treeset.

/**
 * 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; }
 * }
 */
public class SummaryRanges {
    TreeSet<Interval> set;
    /** Initialize your data structure here. */
    public SummaryRanges() {
        set = new TreeSet<Interval>(new Comparator<Interval>(){
                            @Override
                            public int compare(Interval i1, Interval i2){
                                return i1.start - i2.start;
                            }
        });
    }
    //whether fast add or fast get
    public void addNum(int val) {
        Interval v = new Interval(val, val);

        Interval f = set.floor(v);
        if(f != null){
            if(f.end >= val) return;
            if(f.end + 1 == val){
                v.start = f.start;
                set.remove(f);
            }
        }

        Interval h = set.higher(v);

        if(h!= null && h.start == val +1){
            v.end = h.end;
            set.remove(h);
        }

        set.add(v);
    }

    public List<Interval> getIntervals() {
        List<Interval> list = new ArrayList<Interval>();
        list.addAll(set);
        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();
 */