{"id":9308,"date":"2021-12-31T05:50:08","date_gmt":"2021-12-31T13:50:08","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9308"},"modified":"2021-12-31T05:55:46","modified_gmt":"2021-12-31T13:55:46","slug":"leetcode-1942-the-number-of-the-smallest-unoccupied-chair","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/priority-queue\/leetcode-1942-the-number-of-the-smallest-unoccupied-chair\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1942. The Number of the Smallest Unoccupied Chair"},"content":{"rendered":"\n<p>There is a party where&nbsp;<code>n<\/code>&nbsp;friends numbered from&nbsp;<code>0<\/code>&nbsp;to&nbsp;<code>n - 1<\/code>&nbsp;are attending. There is an&nbsp;<strong>infinite<\/strong>&nbsp;number of chairs in this party that are numbered from&nbsp;<code>0<\/code>&nbsp;to&nbsp;<code>infinity<\/code>. When a friend arrives at the party, they sit on the unoccupied chair with the&nbsp;<strong>smallest number<\/strong>.<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>For example, if chairs&nbsp;<code>0<\/code>,&nbsp;<code>1<\/code>, and&nbsp;<code>5<\/code>&nbsp;are occupied when a friend comes, they will sit on chair number&nbsp;<code>2<\/code>.<\/li><\/ul>\n\n\n\n<p>When a friend leaves the party, their chair becomes unoccupied at the moment they leave. If another friend arrives at that same moment, they can sit in that chair.<\/p>\n\n\n\n<p>You are given a&nbsp;<strong>0-indexed<\/strong>&nbsp;2D integer array&nbsp;<code>times<\/code>&nbsp;where&nbsp;<code>times[i] = [arrival<sub>i<\/sub>, leaving<sub>i<\/sub>]<\/code>, indicating the arrival and leaving times of the&nbsp;<code>i<sup>th<\/sup><\/code>&nbsp;friend respectively, and an integer&nbsp;<code>targetFriend<\/code>. All arrival times are&nbsp;<strong>distinct<\/strong>.<\/p>\n\n\n\n<p>Return<em>&nbsp;the&nbsp;<strong>chair number<\/strong>&nbsp;that the friend numbered&nbsp;<\/em><code>targetFriend<\/code><em>&nbsp;will sit on<\/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> times = [[1,4],[2,3],[4,6]], targetFriend = 1\n<strong>Output:<\/strong> 1\n<strong>Explanation:<\/strong> \n- Friend 0 arrives at time 1 and sits on chair 0.\n- Friend 1 arrives at time 2 and sits on chair 1.\n- Friend 1 leaves at time 3 and chair 1 becomes empty.\n- Friend 0 leaves at time 4 and chair 0 becomes empty.\n- Friend 2 arrives at time 4 and sits on chair 0.\nSince friend 1 sat on chair 1, we return 1.\n<\/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> times = [[3,10],[1,5],[2,6]], targetFriend = 0\n<strong>Output:<\/strong> 2\n<strong>Explanation:<\/strong> \n- Friend 1 arrives at time 1 and sits on chair 0.\n- Friend 2 arrives at time 2 and sits on chair 1.\n- Friend 0 arrives at time 3 and sits on chair 2.\n- Friend 1 leaves at time 5 and chair 0 becomes empty.\n- Friend 2 leaves at time 6 and chair 1 becomes empty.\n- Friend 0 leaves at time 10 and chair 2 becomes empty.\nSince friend 0 sat on chair 2, we return 2.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>n == times.length<\/code><\/li><li><code>2 &lt;= n &lt;= 10<sup>4<\/sup><\/code><\/li><li><code>times[i].length == 2<\/code><\/li><li><code>1 &lt;= arrival<sub>i<\/sub>&nbsp;&lt; leaving<sub>i<\/sub>&nbsp;&lt;= 10<sup>5<\/sup><\/code><\/li><li><code>0 &lt;= targetFriend &lt;= n - 1<\/code><\/li><li>Each&nbsp;<code>arrival<sub>i<\/sub><\/code>&nbsp;time is&nbsp;<strong>distinct<\/strong>.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Treeset + Simulation<\/strong><\/h2>\n\n\n\n<p>Use a treeset to track available chairs, sort events by time.<br>note: process leaving events first.<\/p>\n\n\n\n<p>Time complexity: O(nlogn)<br>Space complexity: O(n)<\/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  int smallestChair(vector<vector<int>>& times, int targetFriend) {\n    const int n = times.size();\n    vector<pair<int, int>> arrival(n);\n    vector<pair<int, int>> leaving(n);\n    for (int i = 0; i < n; ++i) {\n      arrival[i] = {times[i][0], i};\n      leaving[i] = {times[i][1], i};\n    }\n    vector<int> pos(n);\n    iota(begin(pos), end(pos), 0); \/\/ pos = [0, 1, ..., n -1]\n    set<int> aval(begin(pos), end(pos));    \n    sort(begin(arrival), end(arrival));\n    sort(begin(leaving), end(leaving));\n    for (int i = 0, j = 0; i < n; ++i) {\n      const auto [t, u] = arrival[i];\n      while (j < n &#038;&#038; leaving[j].first <= t)        \n        aval.insert(pos[leaving[j++].second]);        \n      aval.erase(pos[u] = *begin(aval));      \n      if (u == targetFriend) return pos[u];\n    }\n    return -1;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>There is a party where&nbsp;n&nbsp;friends numbered from&nbsp;0&nbsp;to&nbsp;n &#8211; 1&nbsp;are attending. There is an&nbsp;infinite&nbsp;number of chairs in this party that are numbered from&nbsp;0&nbsp;to&nbsp;infinity. When a friend&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[674],"tags":[724,73,177,15,656],"class_list":["post-9308","post","type-post","status-publish","format-standard","hentry","category-priority-queue","tag-events","tag-heap","tag-medium","tag-sorting","tag-treeset","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9308","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=9308"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9308\/revisions"}],"predecessor-version":[{"id":9310,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9308\/revisions\/9310"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9308"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9308"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9308"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}