Advanced Two Pointer problem

Leetcode 1847 Closest Room

This two pointer problem is the 4th problem of last week’s biweekly contest problem.

Explanation

Sort the query by minSize. Sort the room by size.

Then one pass to check the query from maximum minSize and add the satisified rooms whose size is larger than the required size into a set.

I remember there is a similar problem before, I forget that problem. I will add that paoblem in this article when I find it.

Complexity

Two Sorts: O(m log m), O(n log n)

After sorting, when find the results, we are searching from a balanced binary search tree (set in C++), the complexity is O(n log m).

Overrall complexity is O(K log K) where K is max(n, m).

1847. Closest Room

const int INF = 1e9;
struct Query{
    int id, prefered, minSize;
    bool operator< (const Query& b) {
        return minSize < b.minSize; 
    }
};
class Solution {
public:
    vector<int> closestRoom(vector<vector<int>>& rooms, vector<vector<int>>& queries) {
        const int n = queries.size(), m = rooms.size();
        vector<int> ret(n, -1);
        vector<Query> q;
        q.reserve(n);
        for (int i = 0; i < n; ++i){
            q.push_back({i, queries[i][0], queries[i][1]});
        }
        sort(q.begin(), q.end());
        sort(rooms.begin(), rooms.end(), [](const vector<int> &a, const vector<int> &b) {
            return a[1] < b[1];
        });
        set<int> S={-INF, INF};
        int i = m;
        for (int j = n -1; j >= 0; --j) {
            auto minSize = q[j].minSize;
            while (i - 1 >= 0 and rooms[i-1][1] >= minSize ) {
                S.insert(rooms[i-1][0]);
                --i;
            }
            auto prefered = q[j].prefered;
            auto it = S.upper_bound(prefered);
            auto thisRet = abs(*it - prefered) < abs(*prev(it) - prefered) ? *it : *(prev(it));
            if (abs(thisRet) != INF) ret[q[j].id] = thisRet; 
        }
        return ret;
    }
};