Design a class SummaryRanges that adds integers one by one and returns the disjoint sorted list of intervals they form.
addNum(1)→[[1,1]], addNum(3)→[[1,1],[3,3]], addNum(7)→[[1,1],[3,3],[7,7]], addNum(2)→[[1,3],[7,7]], addNum(6)→[[1,3],[6,7]]
Use a TreeMap. When adding a number, merge with any overlapping or adjacent intervals.
- TreeMap: key=start, value=end.
- On addNum(val): if already covered, skip.
- Find floor and ceiling entries. Merge with floor if floor.end >= val-1. Merge with ceiling if ceil.start <= val+1.
- Insert/update merged interval.
import java.util.*;
class SummaryRanges {
TreeMap<Integer,Integer> map = new TreeMap<>();
public void addNum(int val) {
if (map.floorKey(val) != null && map.get(map.floorKey(val)) >= val) return;
int start = val, end = val;
Integer lo = map.floorKey(val), hi = map.ceilingKey(val);
if (lo != null && map.get(lo) >= val - 1) { start = lo; end = Math.max(end, map.get(lo)); map.remove(lo); }
if (hi != null && hi <= val + 1) { end = Math.max(end, map.get(hi)); map.remove(hi); }
map.put(start, end);
}
public int[][] getIntervals() {
int[][] res = new int[map.size()][2];
int i = 0;
for (Map.Entry<Integer,Integer> e : map.entrySet()) { res[i][0]=e.getKey(); res[i++][1]=e.getValue(); }
return res;
}
}
- Time Complexity: addNum: O(log N), getIntervals: O(N)
- Space Complexity: O(N)