{"id":8419,"date":"2021-05-01T16:01:00","date_gmt":"2021-05-01T23:01:00","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8419"},"modified":"2021-05-02T13:17:09","modified_gmt":"2021-05-02T20:17:09","slug":"leetcode-1847-closest-room","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/binary-search\/leetcode-1847-closest-room\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1847. Closest Room"},"content":{"rendered":"\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1847. Closest Room - \u5237\u9898\u627e\u5de5\u4f5c EP393\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/JQTV3yzSBZE?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>There is a hotel with&nbsp;<code>n<\/code>&nbsp;rooms. The rooms are represented by a 2D integer array&nbsp;<code>rooms<\/code>&nbsp;where&nbsp;<code>rooms[i] = [roomId<sub>i<\/sub>, size<sub>i<\/sub>]<\/code>&nbsp;denotes that there is a room with room number&nbsp;<code>roomId<sub>i<\/sub><\/code>&nbsp;and size equal to&nbsp;<code>size<sub>i<\/sub><\/code>. Each&nbsp;<code>roomId<sub>i<\/sub><\/code>&nbsp;is guaranteed to be&nbsp;<strong>unique<\/strong>.<\/p>\n\n\n\n<p>You are also given&nbsp;<code>k<\/code>&nbsp;queries in a 2D array&nbsp;<code>queries<\/code>&nbsp;where&nbsp;<code>queries[j] = [preferred<sub>j<\/sub>, minSize<sub>j<\/sub>]<\/code>. The answer to the&nbsp;<code>j<sup>th<\/sup><\/code>&nbsp;query is the room number&nbsp;<code>id<\/code>&nbsp;of a room such that:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>The room has a size of&nbsp;<strong>at least<\/strong>&nbsp;<code>minSize<sub>j<\/sub><\/code>, and<\/li><li><code>abs(id - preferred<sub>j<\/sub>)<\/code>&nbsp;is&nbsp;<strong>minimized<\/strong>, where&nbsp;<code>abs(x)<\/code>&nbsp;is the absolute value of&nbsp;<code>x<\/code>.<\/li><\/ul>\n\n\n\n<p>If there is a&nbsp;<strong>tie<\/strong>&nbsp;in the absolute difference, then use the room with the&nbsp;<strong>smallest<\/strong>&nbsp;such&nbsp;<code>id<\/code>. If there is&nbsp;<strong>no such room<\/strong>, the answer is&nbsp;<code>-1<\/code>.<\/p>\n\n\n\n<p>Return&nbsp;<em>an array&nbsp;<\/em><code>answer<\/code><em>&nbsp;of length&nbsp;<\/em><code>k<\/code><em>&nbsp;where&nbsp;<\/em><code>answer[j]<\/code><em>&nbsp;contains the answer to the&nbsp;<\/em><code>j<sup>th<\/sup><\/code><em>&nbsp;query<\/em>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> rooms = [[2,2],[1,2],[3,2]], queries = [[3,1],[3,3],[5,2]]\n<strong>Output:<\/strong> [3,-1,3]\n<strong>Explanation: <\/strong>The answers to the queries are as follows:\nQuery = [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.\nQuery = [3,3]: There are no rooms with a size of at least 3, so the answer is -1.\nQuery = [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.<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> rooms = [[1,4],[2,3],[3,5],[4,1],[5,2]], queries = [[2,3],[2,4],[2,5]]\n<strong>Output:<\/strong> [2,1,3]\n<strong>Explanation: <\/strong>The answers to the queries are as follows:\nQuery = [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.\nQuery = [2,4]: Room numbers 1 and 3 both have sizes of at least 4. The answer is 1 since it is smaller.\nQuery = [2,5]: Room number 3 is the only room with a size of at least 5. The answer is 3.<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>n == rooms.length<\/code><\/li><li><code>1 &lt;= n &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>k == queries.length<\/code><\/li><li><code>1 &lt;= k &lt;= 10<sup>4<\/sup><\/code><\/li><li><code>1 &lt;= roomId<sub>i<\/sub>, preferred<sub>j<\/sub>&nbsp;&lt;= 10<sup>7<\/sup><\/code><\/li><li><code>1 &lt;= size<sub>i<\/sub>, minSize<sub>j<\/sub>&nbsp;&lt;= 10<sup>7<\/sup><\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Off Processing: Sort + Binary Search<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><a href=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/05\/1847-ep393-1.png\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/05\/1847-ep393-1.png\" alt=\"\" class=\"wp-image-8423\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/05\/1847-ep393-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/05\/1847-ep393-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/05\/1847-ep393-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><a href=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/05\/1847-ep393-2.png\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/05\/1847-ep393-2.png\" alt=\"\" class=\"wp-image-8424\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/05\/1847-ep393-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/05\/1847-ep393-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/05\/1847-ep393-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/figure>\n\n\n\n<p>Time complexity: O(nlogn + mlogm)<br>Space complexity: O(n + m)<\/p>\n\n\n\n<p>Sort queries and rooms by size in descending order, only add valid rooms (size &gt;= min_size) to the treeset for binary search.<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector<int> closestRoom(vector<vector<int>>& rooms, vector<vector<int>>& queries) {\n    const int n = rooms.size();\n    const int m = queries.size();\n    for (int i = 0; i < m; ++i)\n      queries[i].push_back(i);\n    \/\/ Sort queries by size DESC.\n    sort(begin(queries), end(queries), [](const auto&#038; q1, const auto&#038; q2){\n      return q1[1] > q2[1];\n    });\n    \/\/ Sort room by size DESC.\n    sort(begin(rooms), end(rooms), [](const auto& r1, const auto& r2) {\n      return r1[1] > r2[1];\n    });\n    vector<int> ans(m); \n    int j = 0;\n    set<int> ids;\n    for (const auto& q : queries) {\n      while (j < n &#038;&#038; rooms[j][1] >= q[1])\n        ids.insert(rooms[j++][0]);      \n      if (ids.empty()) {\n        ans[q[2]] = -1;\n        continue;\n      }\n      const int id = q[0];\n      auto it = ids.lower_bound(id);\n      int id1 = (it != end(ids)) ? *it : INT_MAX;\n      int id2 = id1;\n      if (it != begin(ids))\n        id2 = *prev(it);\n      ans[q[2]] = abs(id1 - id) < abs(id2 - id) ? id1 : id2;\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: Fenwick Tree<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><a href=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/05\/1847-ep393-3.png\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/05\/1847-ep393-3.png\" alt=\"\" class=\"wp-image-8425\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/05\/1847-ep393-3.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/05\/1847-ep393-3-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/05\/1847-ep393-3-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/figure>\n\n\n\n<p>Time complexity: O(nlogS + mlogSlogn)<br>Space complexity: O(nlogS)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\nclass Solution {\npublic:\n  vector<int> closestRoom(vector<vector<int>>& rooms,\n                          vector<vector<int>>& queries) {    \n    S = 0;\n    for (const auto& r : rooms) S = max(S, r[1]); \n    for (const auto& r : rooms) update(r[1], r[0]);    \n    vector<int> ans;\n    for (const auto& q : queries)\n      ans.push_back(query(q[1], q[0]));\n    return ans;\n  }\nprivate:\n  int S;\n  void update(int s, int id) {\n    for (s = S - s + 1; s <= S; s += s &#038; (-s))\n      tree[s].insert(id);\n  }\n  \n  int query(int s, int id) {\n    int ans = -1;\n    for (s = S - s + 1; s > 0; s -= s & (-s)) {\n      if (!tree.count(s)) continue;\n      int id1 = INT_MAX;      \n      int id2 = INT_MAX;\n      auto it = tree[s].lower_bound(id);\n      if (it != end(tree[s])) id1 = *it;      \n      if (it != begin(tree[s])) id2 = *prev(it);      \n      int cid = (abs(id1 - id) < abs(id2 - id)) ? id1 : id2;\n      if (ans == -1 || abs(cid - id) < abs(ans - id))\n        ans = cid;\n      else if (abs(cid - id) == abs(ans - id))\n        ans = min(ans, cid);\n    }\n    return ans;\n  }\n  unordered_map<int, set<int>> tree;\n};\n\n\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>There is a hotel with&nbsp;n&nbsp;rooms. The rooms are represented by a 2D integer array&nbsp;rooms&nbsp;where&nbsp;rooms[i] = [roomIdi, sizei]&nbsp;denotes that there is a room with room number&nbsp;roomIdi&nbsp;and&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[149],"tags":[52,217,711],"class_list":["post-8419","post","type-post","status-publish","format-standard","hentry","category-binary-search","tag-binary-search","tag-hard","tag-offline-processing","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8419","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8419"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8419\/revisions"}],"predecessor-version":[{"id":8426,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8419\/revisions\/8426"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8419"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8419"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8419"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}