import bisect
class TimeMap:
def __init__(self):
# 两个并列字典, 其中value顺序对应上
self.value_map = collections.defaultdict(list)
self.time_map = collections.defaultdict(list)
def set(self, key: str, value: str, timestamp: int) -> None:
self.value_map[key].append(value)
self.time_map[key].append(timestamp)
def get(self, key: str, timestamp: int) -> str:
if key not in self.value_map:
return ''
key_time = self.time_map[key]
# bisect 输出: 第一个比timestamp大的index
index = bisect.bisect(key_time, timestamp)
if index >= 1: # 注意输出
return self.value_map[key][index - 1]
return ''