Problem Statement

here is a hotel with n rooms. The rooms are represented by a 2D integer array rooms where rooms[i] = [roomIdi, sizei] denotes that there is a room with room number roomIdi and size equal to sizei. Each roomIdi is guaranteed to be unique.

You are also given k queries in a 2D array queries where queries[j] = [preferredj, minSizej]. The answer to the jth query is the room number id of a room such that:

• The room has a size of at least minSizej, and
• abs(id - preferredj) is minimized, where abs(x) is the absolute value of x.

If there is a tie in the absolute difference, then use the room with the smallest such id. If there is no such room, the answer is -1.

Return an array answer of length k where answer[j] contains the answer to the jth query.

Example 1:

Input: rooms = [[2,2],[1,2],[3,2]], queries = [[3,1],[3,3],[5,2]]
Output: [3,-1,3]
Explanation:The answers to the queries are as follows:
Query = [3,1]: Room number 3 is the closest as abs(3 - 3) = 0, and its size of 2 is at least 1. The answer is 3.
Query = [3,3]: There are no rooms with a size of at least 3, so the answer is -1.
Query = [5,2]: Room number 3 is the closest as abs(3 - 5) = 2, and its size of 2 is at least 2. The answer is 3.

Example 2:

Input: rooms = [[1,4],[2,3],[3,5],[4,1],[5,2]], queries = [[2,3],[2,4],[2,5]]
Output: [2,1,3]
Explanation:The answers to the queries are as follows:
Query = [2,3]: Room number 2 is the closest as abs(2 - 2) = 0, and its size of 3 is at least 3. The answer is 2.
Query = [2,4]: Room numbers 1 and 3 both have sizes of at least 4. The answer is 1 since it is smaller.
Query = [2,5]: Room number 3 is the only room with a size of at least 5. The answer is 3.

Problem Link

Closest Room - LeetCode

Code

class Solution {
public:
   static bool compare(vector<int>& v1,vector<int>& v2) {
        return v1[1]>v2[1];
    }
    vector<int> closestRoom(vector<vector<int>>& rooms, vector<vector<int>>& queries) {
        
        set<int> st; //stores the room ids
        for(int i=0;i<queries.size();i++)
            queries[i].push_back(i);
        
        sort(rooms.begin(),rooms.end(),compare);
        sort(queries.begin(),queries.end(),compare);
        
        int i = 0;
        vector<int> ans(queries.size());
        for(auto q:queries)
        {
            int prefer = q[0],minSize = q[1],idx = q[2];
            
            while(i<rooms.size()&&minSize<=rooms[i][1])
                st.insert(rooms[i++][0]);
            
            if(st.size())
            {
                auto itr = st.upper_bound(prefer);
                
                int res = itr!=st.end() ? abs(prefer-*itr) : INT_MAX;
                int resRoomId = itr != st.end() ? *itr : INT_MAX;
                if(itr!=st.begin())
                {
                    itr--;
                    if(abs(prefer-*itr)<=res)
                       resRoomId = *itr; 
                }
                ans[idx] = resRoomId;
            }
            else
                ans[idx] = -1;
        }
        
        return ans;
        
    }
};