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?
思路： 给定一个数据流，输入一组非负整数a1, a2, …, an, …, 对截止到当前的不相交区间进行汇总。
利用TreeSet数据结构，将不相交区间Interval存储在TreeSet中。 TreeSet底层使用红黑树实现，可以用log(n)的代价实现元素查找。 每次执行addNum操作时，利用TreeSet找出插入元素val的左近邻元素floor（start值不大于val的最大Interval），以及右近邻元素higher（start值严格大于val的最小Interval） 然后根据floor, val, higher之间的关系决定是否对三者进行合并。
/** * Definition for an interval. * public class Interval { * int start; * int end; * Interval() { start = 0; end = 0; } * Interval(int s, int e) { start = s; end = e; } * } */ class SummaryRanges { /** Initialize your data structure here. */ private TreeSet<Interval> intervalSet; public SummaryRanges() { intervalSet = new TreeSet<Interval>(new Comparator<Interval>() { public int compare(Interval a, Interval b) { return a.start - b.start; } }); } public void addNum(int val) { Interval valInterval = new Interval(val, val); Interval floor = intervalSet.floor(valInterval); if (floor != null) { if (floor.end >= val) { return; } else if (floor.end + 1 == val) { valInterval.start = floor.start; intervalSet.remove(floor); } } Interval higher = intervalSet.higher(valInterval); if (higher != null && higher.start == val + 1) { valInterval.end = higher.end; intervalSet.remove(higher); } intervalSet.add(valInterval); } public List<Interval> getIntervals() { return Arrays.asList(intervalSet.toArray(new Interval[0])); } } /** * Your SummaryRanges object will be instantiated and called as such: * SummaryRanges obj = new SummaryRanges(); * obj.addNum(val); * List<Interval> param_2 = obj.getIntervals(); */