- Data Stream as Disjoint Intervals
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?
Credits:
Special thanks to @yunhong for adding this problem and creating most of the test cases.
my thoughts:
1. when add new num, check all previous Intervals.
my solution:
**********
# Definition for an interval.
# class Interval:
# def __init__(self, s=0, e=0):
# self.start = s
# self.end = e
class SummaryRanges:
def __init__(self):
"""
Initialize your data structure here.
"""
self.list = []
def addNum(self, val):
"""
:type val: int
:rtype: void
"""
if not self.list:
self.list.append(Interval(val, val))
else:
temp = (None, -1)
for i, it in enumerate(self.list):
if it.start <= val <= it.end:
temp = (None, 1)
break
if val == it.start - 1:
if temp[0] == None:
it.start -= 1
temp = (it, i)
else:
pre = self.list[temp[1]]
pre.end = it.end
self.list.remove(it)
break
elif val == it.end + 1:
if temp[0] == None:
it.end += 1
temp = (it, i)
else:
pre = self.list[temp[1]]
pre.start = it.start
self.list.remove(it)
break
if temp[1] == -1:
self.list.append(Interval(val, val))
def getIntervals(self):
"""
:rtype: List[Interval]
"""
return sorted(self.list, key = lambda x : x.start)
# Your SummaryRanges object will be instantiated and called as such:
# obj = SummaryRanges()
# obj.addNum(val)
# param_2 = obj.getIntervals()
**********
# Definition for an interval.
# class Interval:
# def __init__(self, s=0, e=0):
# self.start = s
# self.end = e
class SummaryRanges:
def __init__(self):
"""
Initialize your data structure here.
"""
self.list = []
def addNum(self, val):
"""
:type val: int
:rtype: void
"""
if not self.list:
self.list.append(Interval(val, val))
else:
for i, it in enumerate(self.list):
if val < it.start - 1:
self.list.append(Interval(val, val))
self.list.sort(key = lambda x : x.start)
break
if it.start <= val <= it.end:
break
if val == it.start - 1:
it.start -= 1
break
if val == it.end + 1:
if i < len(self.list) - 1 and val >= self.list[i + 1].start - 1:
it.end = self.list[i + 1].end
self.list.remove(self.list[i + 1])
break
else:
it.end += 1
break
if val > self.list[-1].end + 1:
self.list.append(Interval(val, val))
def getIntervals(self):
"""
:rtype: List[Interval]
"""
return self.list
# Your SummaryRanges object will be instantiated and called as such:
# obj = SummaryRanges()
# obj.addNum(val)
# param_2 = obj.getIntervals()
my comments:
from other ppl's solution:
1. Use TreeMap to easily find the lower and higher keys, the key is the start of the interval.
Merge the lower and higher intervals when necessary. The time complexity for adding is O(logN) since lowerKey(), higherKey(), put() and remove() are all O(logN). It would be O(N) if you use an ArrayList and remove an interval from it.
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());
}
}
2. simple python solution with binary search
class SummaryRanges(object):
def __init__(self):
self.intervals = []
def addNum(self, val):
# find location
low, high = 0, len(self.intervals) - 1
while low <= high:
mid = (low + high) // 2
elem = self.intervals[mid]
if elem.start <= val <= elem.end:
return
elif elem.start > val:
high = mid - 1
else:
low = mid + 1
# insert the interval
pos = min(low, high) + 1
self.intervals[pos:pos] = [Interval(val, val)]
# merge with next interval
if pos + 1 < len(self.intervals) and val == self.intervals[pos + 1].start - 1:
self.intervals[pos].end = self.intervals[pos + 1].end
self.intervals[pos + 1:pos + 2] = []
# merge with prev interval
if pos - 1 >= 0 and val == self.intervals[pos - 1].end + 1:
self.intervals[pos - 1].end = self.intervals[pos].end
self.intervals[pos:pos + 1] = []
def getIntervals(self):
return self.intervals