LSM run merging
Your task
An LSM engine flushes a memtable and several on-disk SSTables, each given to you as a list of [key, value] pairs already sorted ascending by key. Runs are ordered oldest-first; the LAST run in the input is the newest. Merge them into a single sorted run where, for any key present in multiple runs, the value from the newest run wins. Return the merged list of [key, value] pairs sorted ascending by key. Keys are strings; total pairs across runs <= 10^5.
Examples
lsm_merge(runs: list[list[list]]) -> list[list]Example 1
Input
lsm_merge([[["a", 1], ["c", 3]], [["b", 2], ["c", 9]]])Output
[["a", 1], ["b", 2], ["c", 9]]