981. Time Based Key-Value Store

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

实现支持根据时间查询的map: set(string key, string value, int timestamp)和get(string key, int timestam。注意这道题和另一道让实现key带TTL的map题不一样。对每个key维持一个根据ts不断插入的List，然后二分找小于ts的value。或对每个key维持一个tree map, upper_bound(ts)找到第一个大于ts的value，prev一下就是最后一个小于ts的。tree map的insertion时间消耗为O(lgN)，比list的O(1)长。

class Solution {
public:
    int minManHaDis(vector<vector<int>> &ws, vector<vector<int>> &bs) {
        int m = ws.size(), n = bs.size();//m <= n based on the question;
        vector<vector<int>> memo(1<<m, vector<int>(1<<n, -1));
        int state1 = 0, state2 = 0;
        int res = dfs(0, ws, state1, bs, state2, memo);
        //cout<<res<<endl;
        return res;
    }
 
private:
    int dfs(int i, vector<vector<int>> &ws, int st1, vector<vector<int>> &bs, int st2, vector<vector<int>> &memo) {
        if(i==ws.size()) return 0;//all the workers are assigned;
        if(memo[st1][st2] != -1) return memo[st1][st2];//calculated;
        int min_dis = INT_MAX;
        for(int j = 0; j < bs.size(); ++j) {//try all the bikes;
            if((st2>>j) & 1) continue;//if the bike is used;
            int one_dis = abs(ws[i][0] - bs[j][0]) + abs(ws[i][1] - bs[j][1]);
            one_dis += dfs(i+1, ws, st1 | (1<<i), bs, st2 | (1<<j), memo);//total dis in this case;
            min_dis = min(min_dis, dis);//min distance;
        }
        return memo[st1][st2] = min_dis;//memorize min distance;
    }
};