{"id":3374,"date":"2018-07-29T14:28:53","date_gmt":"2018-07-29T21:28:53","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=3374"},"modified":"2018-07-29T14:58:42","modified_gmt":"2018-07-29T21:58:42","slug":"leetcode-855-exam-room","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/simulation\/leetcode-855-exam-room\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 855. Exam Room"},"content":{"rendered":"<h1><strong>Problem<\/strong><\/h1>\n<p>In an exam room, there are\u00a0<code>N<\/code>\u00a0seats in a single row, numbered\u00a0<code>0, 1, 2, ..., N-1<\/code>.<\/p>\n<p>When a student enters the room, they must sit in the seat that maximizes the distance to the closest person.\u00a0 If there are multiple such seats, they sit in the seat with the lowest number.\u00a0 (Also, if no one is in the room, then the student sits at seat number 0.)<\/p>\n<p>Return a class\u00a0<code>ExamRoom(int N)<\/code>\u00a0that exposes two functions:\u00a0<code>ExamRoom.seat()<\/code>\u00a0returning an\u00a0<code>int<\/code>\u00a0representing what seat the student sat in, and\u00a0<code>ExamRoom.leave(int p)<\/code>\u00a0representing that the student in seat number\u00a0<code>p<\/code>\u00a0now leaves the room.\u00a0 It is guaranteed that any calls to\u00a0<code>ExamRoom.leave(p)<\/code>\u00a0have a student sitting in seat\u00a0<code>p<\/code>.<\/p>\n<p><strong>Example 1:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input: <\/strong><span id=\"example-input-1-1\">[\"ExamRoom\",\"seat\",\"seat\",\"seat\",\"seat\",\"leave\",\"seat\"]<\/span>, <span id=\"example-input-1-2\">[[10],[],[],[],[],[4],[]]<\/span>\r\n<strong>Output: <\/strong><span id=\"example-output-1\">[null,0,9,4,2,null,5]<\/span>\r\n<strong>Explanation<\/strong>:\r\nExamRoom(10) -&gt; null\r\nseat() -&gt; 0, no one is in the room, then the student sits at seat number 0.\r\nseat() -&gt; 9, the student sits at the last seat number 9.\r\nseat() -&gt; 4, the student sits at the last seat number 4.\r\nseat() -&gt; 2, the student sits at the last seat number 2.\r\nleave(4) -&gt; null\r\nseat() -&gt; 5, the student\u200b\u200b\u200b\u200b\u200b\u200b\u200b sits at the last seat number 5.\r\n<\/pre>\n<p>\u200b\u200b\u200b\u200b<strong>Note:<\/strong><\/p>\n<ol>\n<li><code>1 &lt;= N &lt;= 10^9<\/code><\/li>\n<li><code>ExamRoom.seat()<\/code>\u00a0and\u00a0<code>ExamRoom.leave()<\/code>\u00a0will be called at most\u00a0<code>10^4<\/code>\u00a0times across all test cases.<\/li>\n<li>Calls to\u00a0<code>ExamRoom.leave(p)<\/code>\u00a0are guaranteed to have a student currently sitting in seat number\u00a0<code>p<\/code>.<\/li>\n<\/ol>\n<h1><strong>Solution: BST<\/strong><\/h1>\n<p>Use a BST (ordered set) to track the current seatings.<\/p>\n<p>Time Complexity:<\/p>\n<p>init: O(1)<\/p>\n<p>seat: O(P)<\/p>\n<p>leave: O(logP)<\/p>\n<p>Space complexity: O(P)<\/p>\n<pre class=\"lang:default decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 24 ms\r\nclass ExamRoom {\r\npublic:\r\n  ExamRoom(int N): N_(N) {}\r\n\r\n  int seat() {\r\n    int p = 0;\r\n    int max_dist = s_.empty() ? 0 : *s_.begin();\r\n    auto left = s_.begin();    \r\n    auto right = left;\r\n    while (left != s_.end()) {\r\n      ++right;\r\n      int l = *left;\r\n      int r = right != s_.end() ? *right : (2 * (N_ - 1) - *left);      \r\n      int d = (r - l) \/ 2;      \r\n      if (d &gt; max_dist) {\r\n        max_dist = d;\r\n        p = l + d;\r\n      }\r\n      left = right;\r\n    }    \r\n    s_.insert(p);\r\n    return p;\r\n  }\r\n\r\n  void leave(int p) {\r\n    s_.erase(p);\r\n  }\r\n\r\nprivate:\r\n  const int N_;\r\n  set&lt;int&gt; s_;\r\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem In an exam room, there are\u00a0N\u00a0seats in a single row, numbered\u00a00, 1, 2, &#8230;, N-1. When a student enters the room, they must sit&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48],"tags":[74,177,243,179],"class_list":["post-3374","post","type-post","status-publish","format-standard","hentry","category-simulation","tag-bst","tag-medium","tag-set","tag-simulation","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3374","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=3374"}],"version-history":[{"count":5,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3374\/revisions"}],"predecessor-version":[{"id":3379,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3374\/revisions\/3379"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3374"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3374"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3374"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}