Data Stream as Disjoint Intervals
给一个intervals的stream, 求写一个API. 这个要利用java treemap的内建方法.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
public class SummaryRanges { TreeMap<Integer, Interval> tree; public SummaryRanges() { tree = new TreeMap<>(); } public void addNum(int val) { if(tree.containsKey(val)) return; Integer l = tree.lowerKey(val); Integer h = tree.higherKey(val); if(l != null && h != null && tree.get(l).end + 1 == val && h == val + 1) { tree.get(l).end = tree.get(h).end; tree.remove(h); } else if(l != null && tree.get(l).end + 1 >= val) { tree.get(l).end = Math.max(tree.get(l).end, val); } else if(h != null && h == val + 1) { tree.put(val, new Interval(val, tree.get(h).end)); tree.remove(h); } else { tree.put(val, new Interval(val, val)); } } public List<Interval> getIntervals() { return new ArrayList<>(tree.values()); } } |