352. Data Stream as Disjoint Int

My initial solution: 可能产生 merge 的情况集中处理，可以减少代码量。查找处可以使用 Binary Search 优化。

class SummaryRanges {

    ArrayList<Interval> list; 
    
    /** Initialize your data structure here. */
    public SummaryRanges() {
        list = new ArrayList<>();
    }
    
    public void addNum(int val) {
        if (list.size() == 0) {
            list.add(new Interval(val, val));
            return;
        }
        int index = 0;
        while (index < list.size() && list.get(index).start <= val) {
            index++;
        }
        
        index--;
        if (index < 0) {
            Interval first = list.get(0);
            if (first.start == val + 1) {
                // case first interval = [4, 7], val = 3, update first interval to [3, 7]
                first.start = val;
            } else {
                // case first interval = [4, 7], val = 2, add new interval [2, 2] in front of [4, 7]
                list.add(0, new Interval(val, val));
            }
        } else if (index == list.size() - 1) {
            Interval last = list.get(list.size() - 1);
            if (last.end == val - 1) {
                // case last interval = [3, 10], val = 11, update last interval to [3, 11]
                last.end = val;
            } else if (last.end < val - 1) {
                // case last interval = [3, 10], val = 14, add new interva [14, 14] in the end
                list.add(new Interval(val, val));
            } else {
                // case last interval = [3, 10], val = 5 included in the last interval
                // do nothing
            }
        } else {
            Interval curr = list.get(index);
            Interval next = list.get(index + 1);
            
            // here we have curr.start <= val && next.start > val
            
            if (curr.end >= val) {
                // case curr = [3, 5], next = [7, 10], val = 4 included in curr range
                // do nothing
            } else if (curr.end == val - 1){
                if (next.start == curr.end + 2) {
                    // case curr = [3, 5], next = [7, 10], val = 6 connecting curr and next
                    curr.end = next.end;
                    list.remove(next);
                } else {
                    // case curr = [3, 5], next = [8, 10], val = 6 new end for curr
                    curr.end = val;
                }
            } else if (next.start == val + 1) {
                // case curr = [3, 5], next = [8, 10], val = 7 new start for next
                next.start = val;
            } else {
                // case curr = [3, 5], next = [9, 10], val = 7 new interval to be added
                list.add(index + 1, new Interval(val, val));
            }
        }
    }
    
    public List<Interval> getIntervals() {
        return list;
    }
}

YouTube 题解

题解使用了 TreeMap，StartTime => Interval. 之前面试的时候有想过使用 Binary Search Tree 来对 Interval 进行存储，但是没有想好 Data Structure 应该是什么样子的。

TreeMap 的一些性质：

TreeMap 使用 Red-Black Tree 来实现，key ordered

treeMap.lowerKey(target): returns biggest key lower than target
treeMap.higherKey(target): returns smallest key bigger than target
returns null for the two methods above if there is no such key.

Example: TreeMap keys [1, 3, 6, 10], target 7 => lowerKey: 6, higherKey: 10

按 TreeMap 写的 initial Solution，有些逻辑是可以进行合并的。

class SummaryRanges {
    
    TreeMap<Integer, Interval> map;
    
    public SummaryRanges() {
        map = new TreeMap();
    }
    
    public void addNum(int val) {
        if (map.containsKey(val)) {
            return;
        }
        
        Integer lower = map.lowerKey(val);
        Integer higher = map.higherKey(val);
        
        if (lower == null && higher == null) {
            map.put(val, new Interval(val, val));
        } else if (lower != null && higher != null) {
            Interval lowerInterval = map.get(lower);
            Interval higherInterval = map.get(higher);
            if (lowerInterval.end >= val) {
                // do nothing
            } else if (lowerInterval.end + 1 == val) {
                if (higherInterval.start == val + 1) {
                    lowerInterval.end = higherInterval.end;
                    map.remove(higher);
                } else {
                    lowerInterval.end = val;
                }
            } else {
                if (higherInterval.start == val + 1) {
                    higherInterval.start = val;
                    map.put(val, higherInterval);
                    map.remove(higher);
                } else {
                    map.put(val, new Interval(val, val));
                }
            }
        } else if (higher != null) {
            Interval higherInterval = map.get(higher);
            if (higherInterval.start == val + 1) {
                higherInterval.start = val;
                map.put(val, higherInterval);
                map.remove(higher);
            } else {
                map.put(val, new Interval(val, val));
            }
        } else {
            Interval lowerInterval = map.get(lower);
            if (lowerInterval.end >= val) {
                // do nothing
            } else if (lowerInterval.end + 1 == val) {
                lowerInterval.end = val;
            } else {
                map.put(val, new Interval(val, val));
            }
        }
    }
    
    public List<Interval> getIntervals() {
        return new ArrayList<Interval>(map.values());   
    }

Simplified but need to debug:

    public void addNum(int val) {
        if (map.containsKey(val)) {
            return;
        }
        
        Integer lower = map.lowerKey(val);
        Integer higher = map.higherKey(val);
        
        if (lower != null && higher != null) {
            if (map.get(lower).end + 1 == val && map.get(higher).start == val + 1) {
                map.get(lower).end = map.get(higher).end;
                map.remove(higher);
            } else if (map.get(lower).end + 1 == val) {
                map.get(lower).end = val;
            } else if (map.get(higher).start == val + 1) {
                map.put(val, new Interval(val, map.get(higher).end));
                map.remove(higher);
            } else {
                map.put(val, new Interval(val, val));
            }
        } else if (lower != null && higher == null && val <= map.get(lower).end + 1) {
            map.get(lower).end = Math.max(val, map.get(lower).end);
        } else if (lower == null && higher != null && map.get(higher).start == val + 1) {
            map.put(val, new Interval(val, map.get(higher).end));
            map.remove(higher);
        } else {
            map.put(val, new Interval(val, val));
        }
    }