202407071449
tags: #binary-search

var TimeMap = function() {
	this.map = new Map();
};

TimeMap.prototype.set = function(key, value, timestamp) {
	if (!this.map.has(key)) {
		this.map.set(key, []);
	}
	this.map.get(key).push([timestamp, value]);
};

TimeMap.prototype.get = function(key, timestamp) {
	const pairs = this.map.get(key) ?? [];
	let start = 0;
	let end = pairs.length - 1;
	let target = '';
	while (start <= end) {
		const mid = Math.floor((end - start) / 2) + start;
		const [curTimestamp, val] = pairs[mid];
		if (curTimestamp <= timestamp) {
			target = val;
			start = mid + 1;
		} else {
			end = mid - 1;
		}
	}
	return target;
};

Reference

https://leetcode.com/problems/time-based-key-value-store/