Editorial: LeetCode 1847 Closest Room
https://leetcode.com/problems/closest-room/ from Amazon
Thinking process:
At first I was thinking this is a 2D binary search problem as we need to find rooms which has size equal or greater than we request, and then we also want to find the closest room id. However, since all the queries are given already, we can do an offline search instead of online search.
What this means is that we can process the queries in any order we want. Knowing this, we can process the queries from biggest size to smallest size. With this order, we can gradually add rooms into our search space so that at any given time the search space only contains rooms size which is bigger than the query.
For example, at the beginning, we don’t put any rooms into our search space. When we process the biggest query, we put all the rooms, which has a roome size bigger than the query, into the search space.
Like the above example, if our query room size is 5, then we only put rooms which has a room size bigger than 5 into our search space. With this strategy, the only thing we need is to find a room id cloest to the preferred index, which can be done by a binary search.
After this, our query room size might be 3. Then our search space becomes
Here is the code.
1class Solution {
2public:
3 vector<int> closestRoom(vector<vector<int>>& rooms, vector<vector<int>>& queries) {
4 sort(rooms.begin(), rooms.end(), [](const auto& r1, const auto& r2){
5 if (r1[1] != r2[1]) return r1[1] < r2[1];
6 return r1[0] < r2[0];
7 });
8 int R = rooms.size();
9 vector<vector<int>> q;
10 int Q = queries.size();
11 for (int i=0; i<Q; i++) {
12 auto query = queries[i];
13 query.push_back(i);
14 q.push_back(query);
15 }
16 sort(q.begin(), q.end(), [](const auto& r1, const auto& r2){
17 if (r1[1] != r2[1]) return r1[1] < r2[1];
18 return r1[0] < r2[0];
19 });
20 set<int> s;
21 int cur = R - 1;
22 vector<int> ans(Q, -1);
23 for (int i=Q-1; i>=0; i--) {
24 vector<int> query = q[i];
25 int preferred = query[0], size = query[1], index = query[2];
26 while (cur >= 0 and rooms[cur][1] >= size) {
27 s.insert(rooms[cur][0]);
28 cur--;
29 }
30 auto it = s.lower_bound(preferred);
31 if (s.size()) {
32 if (*it == preferred or it == s.begin()) ans[index] = *it;
33 else if (it == s.end()) ans[index] = *prev(it);
34 else {
35 auto it2 = prev(it);
36 if (*it - preferred < preferred - *it2) ans[index] = *it;
37 else ans[index] = *it2;
38 }
39 }
40 }
41 return ans;
42 }
43};