352. Data Stream as Disjoint Intervals (1)

Link

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?

Solution

需要使用treeMap，因為它可方便尋找對映要進行處理的interval

透過lowerKey, higherKey找出可能會受影響的interval進行合併

Treemap<K, V>

K : start(lowest) value of the interval

V: the interval presented by array, [start, end]

class SummaryRanges {

    /** Initialize your data structure here. */
    TreeMap<Integer, int[]> treeMap;
    public SummaryRanges() {
        treeMap = new TreeMap<>();
    }
    
    public void addNum(int val) {
        if(treeMap.containsKey(val)) return;
        Integer lowerKey = treeMap.lowerKey(val);
        Integer higherKey = treeMap.higherKey(val);
        
        //case 1
        //key   value   
        //1     [1,1] 
        //3     [3,3] 
        //-> enter val 2 shall become 
        //1     [1,3]
        if(lowerKey != null && higherKey != null && treeMap.get(lowerKey)[1]+1 == val
          &&  treeMap.get(higherKey)[0]-1 == val){
            treeMap.get(lowerKey)[1] = treeMap.get(higherKey)[1];
            treeMap.remove(higherKey);
        }
        //case 2
        //key   value   
        //1     [1,1] 
        //-> enter val 2 shall become 
        //1     [1,2]
        //
        //case 3
        //key   value   
        //1     [1,3]
        //-> enter val 2 shall become
        //1     [1,3]
        else if(lowerKey != null && 
                (treeMap.get(lowerKey)[1]+1 == val || treeMap.get(lowerKey)[1] >= val))
        {
            treeMap.get(lowerKey)[1] = Math.max(treeMap.get(lowerKey)[1], val);
        }
        //case 4 //rember this case
        //key   value
        // 4    [4, 4]
        // -> enter val 3 shall become
        // 3    [3, 4]
        else if(higherKey != null && treeMap.get(higherKey)[0]-1 == val)
        {
            treeMap.put(val ,new int[]{val, treeMap.get(higherKey)[1]});
            treeMap.remove(higherKey);
        }
        else{
            treeMap.put(val ,new int[]{val, val});
        }
        
    }
    
    public int[][] getIntervals() {
       return treeMap.values().toArray(new int[treeMap.size()][2]);
    }
}