LeetCode 1847. Closest Room

There 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.

Constraints:

• n == rooms.length

• 1 <= n <= 10^5

• k == queries.length

• 1 <= k <= 10^4

• 1 <= roomIdi, preferredj <= 10^7

• 1 <= sizei, minSizej <= 10^7

Solution

English Version in Youtube

中文版解答Youtube Link

中文版解答Bilibili Link

class Solution {
public:
    vector<int> closestRoom(vector<vector<int>>& rooms, vector<vector<int>>& queries) {
        int m = queries.size();
        vector<int> idx(m);
        std::iota(idx.begin(), idx.end(), 0);

        std::sort(idx.begin(), idx.end(), [&queries](int idx1, int idx2) {
            return queries[idx1][1] > queries[idx2][1];
        });
        std::sort(rooms.begin(), rooms.end(), [](const vector<int>& room1, const vector<int>& room2) {
            return room1[1] > room2[1];
        });
        
        vector<int> ans(m, -1);
        int room_idx = 0;
        set<int> valid_rooms;
        for (int e : idx) {
            int preferred = queries[e][0];
            int min_size = queries[e][1];
            
            while (room_idx < rooms.size() && rooms[room_idx][1] >= min_size) {
                valid_rooms.insert(rooms[room_idx][0]);
                room_idx++;
            }
            
            if (valid_rooms.empty()) {
                continue;
            }
            
            auto it = valid_rooms.upper_bound(preferred);
            if (it != valid_rooms.end()) {
                ans[e] = *it;
            }
            if (it != valid_rooms.begin()) {
                it--;
                if (ans[e] == -1) {
                    ans[e] = *it;
                } else if (preferred - *it <= ans[e] - preferred) {
                    ans[e] = *it;
                }
            }
        }
        
        return ans;
    }
};