Store Timestamped Values and Retrieve the Latest Eligible Version

### Problem Implement `TimeMap()`, `set(key,value,timestamp)`, and `get(key,timestamp)`. A set stores a value for that key at that timestamp. A get returns the value from the greatest previously set timestamp not exceeding the query time, or the empty string if none exists. Timestamps of all set calls are strictly increasing; get queries need not be chronological. ```cpp class TimeMap { public: TimeMap(); void set(string key, string value, int timestamp); string get(string key, int timestamp); }; ``` ### Examples **Example 1:** ```text Input: construct TimeMap(); set("a","red",2); get("a",1); get("a",2); set("a","blue",7); get("a",6); get("a",9) Output of get calls: ["","red","red","blue"] Explanation: The version at7 is unavailable to a query at6; queries at1 precede every stored version. ``` **Example 2:** ```text Input: construct TimeMap(); set("x","v1",5); get("y",8); get("x",4); get("x",5) Output of get calls: ["","","v1"] Explanation: Missing keys and times before the first version return the empty string. ``` ### Constraints - `1 <= key.length,value.length <= 100`. - Keys and values contain lowercase English letters and digits. - `1 <= timestamp <= 10^7`. - Timestamps of all set calls are strictly increasing. - At most `2*10^5` total set/get calls occur. ### Contract considerations Only set timestamps are strictly increasing globally. get returns a copied string, not a version index or a new transcript API. ```hint Read the boundary condition Appending works because writes are timestamp-ordered; reads then need the rightmost timestamp within a bound. ``` ### Boundary reminders Only set timestamps are strictly increasing globally. get returns a copied string, not a version index or a new transcript API.