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
2
3
4
5
| [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?
Solution
- 按照各个区间的start, 二分查找target对应的区间
- 合并区间
(Data-Stream-as-Disjoint-Intervals.py) download
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| # Definition for an interval.
# class Interval(object):
# def __init__(self, s=0, e=0):
# self.start = s
# self.end = e
class SummaryRanges(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.intervals = []
def addNum(self, val):
"""
:type val: int
:rtype: void
"""
def upper_bound(nums, target):
# 基于nums[i].start, 二分查找
left, right = 0, len(nums)-1
while left<=right:
mid = (left+right)/2
if nums[mid].start > target:
right = mid-1
else:
left = mid+1
return left
i = upper_bound(self.intervals, val)
# 插入target以后，合并各个intervals
# 新集合的start，end
start, end = val, val
# target 和 intervals[i]有交集
if i !=0 and self.intervals[i-1].end+1 >= val:
i -= 1
while i != len(self.intervals) and end+1 >= self.intervals[i].start:
# 有交集
start = min(start,self.intervals[i].start)
end = max(end,self.intervals[i].end)
del self.intervals[i]
# 插入新的区间
self.intervals.insert(i,Interval(start,end))
def getIntervals(self):
"""
:rtype: List[Interval]
"""
return self.intervals
#Your SummaryRanges object will be instantiated and called as such:
# obj = SummaryRanges()
# obj.addNum(val)
# param_2 = obj.getIntervals()
|