1. Runtime Distribution

2. Submission Details

3. Description

Given a data stream input of non-negative integers a1, a2, ..., an, ..., summarize the numbers seen so far as a list of disjoint intervals.

4. 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]

5. Code

List<Interval> intervals;

public SummaryRanges() {
    intervals = new ArrayList<Interval>();
}

public void addNum(int val) {
    int pos = binarySearch(val);

    if (pos < 0) {
        if (intervals.size() > 0 && val == intervals.get(0).start - 1) {
            intervals.get(0).start = val;
        } else {
            intervals.add(0, new Interval(val, val));
        }
    } else {
        if (val == intervals.get(pos).end + 1) {
            intervals.get(pos).end = val;
        } else if (val > intervals.get(pos).end + 1) {
            intervals.add(pos + 1, new Interval(val, val));
            pos++;
        }
        if (pos + 1 < intervals.size() && intervals.get(pos).end + 1 == intervals.get(pos + 1).start) {
            intervals.get(pos).end = intervals.get(pos + 1).end;
            intervals.remove(pos + 1);
        }
    }
}

public int binarySearch(int n) {
    int end = intervals.size() - 1;
    if (end < 0) {
        return -1;
    }

    int start = 0;
    int mid = 0;
    while (start <= end) {
        mid = ((end - start) >> 1) + start;
        if (n < intervals.get(mid).start) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
    return end;
}

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

TreeMap<Integer, Interval> treeMap;

public SummaryRanges() {
    treeMap = new TreeMap<>();
}

public void addNum(int val) {
    if (treeMap.containsKey(val)) {
        return;
    }

    Integer left = treeMap.lowerKey(val);
    Integer right = treeMap.higherKey(val);

    if (left != null && right != null && treeMap.get(left).end + 1 == val && val + 1 == right) {
        treeMap.get(left).end = treeMap.get(right).end;
        treeMap.remove(right);
    } else if (right != null && val + 1 == right) {
        treeMap.put(val, new Interval(val, treeMap.get(right).end));
        treeMap.remove(right);
    } else if (left != null && treeMap.get(left).end + 1 >= val) {
        treeMap.get(left).end = Math.max(treeMap.get(left).end, val);
    } else {
        treeMap.put(val, new Interval(val, val));
    }
}

public List<Interval> getIntervals() {
    return new ArrayList<>(treeMap.values());
}

6.Test

import java.util.ArrayList;
import java.util.List;

public class LeetCode0352 {

    class Interval {
        int start;
        int end;

        Interval() {
            start = 0;
            end = 0;
        }

        Interval(int s, int e) {
            start = s;
            end = e;
        }
    }

    List<Interval> intervals;

    public LeetCode0352() {
        intervals = new ArrayList<Interval>();
    }

    public void addNum(int val) {
        int pos = binarySearch(val);

        if (pos < 0) {
            if (intervals.size() > 0 && val == intervals.get(0).start - 1) {
                intervals.get(0).start = val;
            } else {
                intervals.add(0, new Interval(val, val));
            }
        } else {
            if (val == intervals.get(pos).end + 1) {
                intervals.get(pos).end = val;
            } else if (val > intervals.get(pos).end + 1) {
                intervals.add(pos + 1, new Interval(val, val));
                pos++;
            }
            if (pos + 1 < intervals.size() && intervals.get(pos).end + 1 == intervals.get(pos + 1).start) {
                intervals.get(pos).end = intervals.get(pos + 1).end;
                intervals.remove(pos + 1);
            }
        }
    }

    public int binarySearch(int n) {
        int end = intervals.size() - 1;
        if (end < 0) {
            return -1;
        }

        int start = 0;
        int mid = 0;
        while (start <= end) {
            mid = ((end - start) >> 1) + start;
            if (n < intervals.get(mid).start) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return end;
    }

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

import java.util.ArrayList;
import java.util.List;
import java.util.TreeMap;

public class LeetCode0352 {

    class Interval {
        int start;
        int end;

        Interval() {
            start = 0;
            end = 0;
        }

        Interval(int s, int e) {
            start = s;
            end = e;
        }
    }

    TreeMap<Integer, Interval> treeMap;

    public LeetCode0352() {
        treeMap = new TreeMap<>();
    }

    public void addNum(int val) {
        if (treeMap.containsKey(val)) {
            return;
        }

        Integer left = treeMap.lowerKey(val);
        Integer right = treeMap.higherKey(val);

        if (left != null && right != null && treeMap.get(left).end + 1 == val && val + 1 == right) {
            treeMap.get(left).end = treeMap.get(right).end;
            treeMap.remove(right);
        } else if (right != null && val + 1 == right) {
            treeMap.put(val, new Interval(val, treeMap.get(right).end));
            treeMap.remove(right);
        } else if (left != null && treeMap.get(left).end + 1 >= val) {
            treeMap.get(left).end = Math.max(treeMap.get(left).end, val);
        } else {
            treeMap.put(val, new Interval(val, val));
        }
    }

    public List<Interval> getIntervals() {
        return new ArrayList<>(treeMap.values());
    }
}