1847. Closest Room

周賽的復盤

我們先根據需求的房型大小排序, 讓需要大房間的人間來看

也將我們可以提供的房型大小進行排序, 讓比較大的房間排在最前面

然後依據需求從大需求開始

我們去檢查可以提供的房型, 只要是大於這個需求的我們就納入set

接著放完後, 我們upper_bound去檢查最靠近喜歡的房型, 不用擔心房型是否會找不到因為可以進這個set的都是大於這個需求的房

找到這個upper_bound記得再把pointer倒退一格看看, 說不定另一個方向的prefer值更高

最後我們在看下一間房型, set依舊保留之前的房型, 這是因為之前的房型都比較大, 所以之後的房子越小也完全沒有問題, 大小夠了, 我們之後也只需要看喜不喜歡

另外這個解法會在一開始就把index的資訊存下來, 這是我比賽時沒有想到的, 花很多時間在做排序

class Solution {
public:
    vector<int> closestRoom(vector<vector<int>>& rooms, vector<vector<int>>& queries) {
        for(int i = 0; i < queries.size();i++)
            queries[i].push_back(i);
        sort(queries.begin(), queries.end(), [](auto &a, auto &b){
            return a[1] > b[1];
        });
        sort(rooms.begin(), rooms.end(), [](auto &a, auto &b){
            return a[1] > b[1];
        });
        int i = 0;
        set<int> st;
        vector<int> res(queries.size());
        for(auto q: queries){
            int prefer = q[0], minSize = q[1], idx = q[2];
            while(i < rooms.size() && rooms[i][1] >= minSize){
                st.insert(rooms[i][0]);
                i++;
            }
            if(st.size()){
                auto it = st.upper_bound(prefer);
                int diff = it != st.end()? abs(*it - prefer): INT_MAX;;
                int resRoomId = it != st.end()? *it : INT_MAX;
                if(it != st.begin()){
                    --it;
                    if(abs(*it - prefer) <= diff){
                        resRoomId = *it;
                    }
                }
                res[idx] = resRoomId;
            }else{
                res[idx] = -1;
            }
           
        }
         return res;
    }
};