352. Data Stream as Disjoint Intervals(ArrayList).java

/**
 * 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 {
    List<Interval> lst;
    /** Initialize your data structure here. */
    public SummaryRanges() {
        lst = new ArrayList<Interval>();
    }
    
    public void addNum(int val) {
        int start = 0;
        int end = lst.size() - 1;
        
        if (lst.isEmpty()) {
            lst.add(new Interval(val, val));
            return;
        }
        
        if (val < lst.get(start).start) {
            if (val == lst.get(start).start - 1)
                lst.get(start).start = val;
            else
                lst.add(0, new Interval(val, val));
            return;
        }
        
        if (val > lst.get(end).end) {
            if (val == lst.get(end).end + 1)
                lst.get(end).end = val;
            else
                lst.add(new Interval(val, val));
            return;
        }
        
        while (start < end - 1) {
            int mid = (start + end) / 2;
            
            if (val >= lst.get(mid).start && val <= lst.get(mid).end) {
                return;
            }
                
            if (val > lst.get(mid).end) {
                start = mid;
                continue;
            }
            
            if (val < lst.get(mid).start) {
                end = mid;
                continue;
            }
        }
        
        if (lst.get(start).end + 1 == val && lst.get(end).start - 1 == val) {
            lst.get(start).end = lst.get(end).end;
            lst.remove(end);
        } else if (lst.get(start).end + 1 == val) {
            lst.get(start).end = val;
        } else if (lst.get(end).start - 1 == val) {
            lst.get(end).start = val;
        } else if (lst.get(start).start <= val && lst.get(start).end >= val) {
            return;
        } else if (lst.get(end).start <= val && lst.get(end).end >= val) {
            return;
        } else {
            lst.add(end, new Interval(val, val));
        }
    }
    
    public List<Interval> getIntervals() {
        return lst;
    }
}

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

352. Data Stream as Disjoint Intervals(TreeMap).java

/*

1. Use TreeSet guaranteed log(n) time cost for the basic operations (add, remove and contains).
   The floor() method returns the greatest element in this set less than or equal to the given element, 
   or null if there is no such element. 
   The higher() method returns the least element in this set strictly greater than the given element, 
   or null if there is no such element. 
   Note: we use higher() instead of ceiling() to exclude the given element.
   
2. Use TreeMap
*/

/**
 * 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 {
    
    TreeMap<Integer, Interval> tree;
    /** Initialize your data structure here. */
    public SummaryRanges() {
        tree = new TreeMap<Integer, Interval>();
    }
    
    public void addNum(int val) {
        if(tree.containsKey(val)) return;
        
        Integer low = tree.lowerKey(val);
        Integer high = tree.higherKey(val);
        
        if(low != null && high != null && tree.get(low).end + 1 == val && high == val + 1){
            tree.get(low).end = tree.get(high).end;
            tree.remove(high);
        } else if (low != null && tree.get(low).end + 1 >= val){
            tree.get(low).end = Math.max(tree.get(low).end, val);
        } else if(high != null && high == val + 1) {
            tree.put(val, new Interval(val, tree.get(high).end));
            tree.remove(high);
        } else {
            tree.put(val, new Interval(val, val));
        }
    }
    
    public List<Interval> getIntervals() {
        return new ArrayList<>(tree.values());
    }
}

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