{"id":9387,"date":"2022-01-01T15:40:32","date_gmt":"2022-01-01T23:40:32","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9387"},"modified":"2022-01-01T16:05:06","modified_gmt":"2022-01-02T00:05:06","slug":"leetcode-1912-design-movie-rental-system","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/data-structure\/leetcode-1912-design-movie-rental-system\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1912. Design Movie Rental System"},"content":{"rendered":"\n<p>You have a movie renting company consisting of&nbsp;<code>n<\/code>&nbsp;shops. You want to implement a renting system that supports searching for, booking, and returning movies. The system should also support generating a report of the currently rented movies.<\/p>\n\n\n\n<p>Each movie is given as a 2D integer array&nbsp;<code>entries<\/code>&nbsp;where&nbsp;<code>entries[i] = [shop<sub>i<\/sub>, movie<sub>i<\/sub>, price<sub>i<\/sub>]<\/code>&nbsp;indicates that there is a copy of movie&nbsp;<code>movie<sub>i<\/sub><\/code>&nbsp;at shop&nbsp;<code>shop<sub>i<\/sub><\/code>&nbsp;with a rental price of&nbsp;<code>price<sub>i<\/sub><\/code>. Each shop carries&nbsp;<strong>at most one<\/strong>&nbsp;copy of a movie&nbsp;<code>movie<sub>i<\/sub><\/code>.<\/p>\n\n\n\n<p>The system should support the following functions:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><strong>Search<\/strong>: Finds the&nbsp;<strong>cheapest 5 shops<\/strong>&nbsp;that have an&nbsp;<strong>unrented copy<\/strong>&nbsp;of a given movie. The shops should be sorted by&nbsp;<strong>price<\/strong>&nbsp;in ascending order, and in case of a tie, the one with the&nbsp;<strong>smaller&nbsp;<\/strong><code>shop<sub>i<\/sub><\/code>&nbsp;should appear first. If there are less than 5 matching shops, then all of them should be returned. If no shop has an unrented copy, then an empty list should be returned.<\/li><li><strong>Rent<\/strong>: Rents an&nbsp;<strong>unrented copy<\/strong>&nbsp;of a given movie from a given shop.<\/li><li><strong>Drop<\/strong>: Drops off a&nbsp;<strong>previously rented copy<\/strong>&nbsp;of a given movie at a given shop.<\/li><li><strong>Report<\/strong>: Returns the&nbsp;<strong>cheapest 5 rented movies<\/strong>&nbsp;(possibly of the same movie ID) as a 2D list&nbsp;<code>res<\/code>&nbsp;where&nbsp;<code>res[j] = [shop<sub>j<\/sub>, movie<sub>j<\/sub>]<\/code>&nbsp;describes that the&nbsp;<code>j<sup>th<\/sup><\/code>&nbsp;cheapest rented movie&nbsp;<code>movie<sub>j<\/sub><\/code>&nbsp;was rented from the shop&nbsp;<code>shop<sub>j<\/sub><\/code>. The movies in&nbsp;<code>res<\/code>&nbsp;should be sorted by&nbsp;<strong>price&nbsp;<\/strong>in ascending order, and in case of a tie, the one with the&nbsp;<strong>smaller&nbsp;<\/strong><code>shop<sub>j<\/sub><\/code>&nbsp;should appear first, and if there is still tie, the one with the&nbsp;<strong>smaller&nbsp;<\/strong><code>movie<sub>j<\/sub><\/code>&nbsp;should appear first. If there are fewer than 5 rented movies, then all of them should be returned. If no movies are currently being rented, then an empty list should be returned.<\/li><\/ul>\n\n\n\n<p>Implement the&nbsp;<code>MovieRentingSystem<\/code>&nbsp;class:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>MovieRentingSystem(int n, int[][] entries)<\/code>&nbsp;Initializes the&nbsp;<code>MovieRentingSystem<\/code>&nbsp;object with&nbsp;<code>n<\/code>&nbsp;shops and the movies in&nbsp;<code>entries<\/code>.<\/li><li><code>List&lt;Integer&gt; search(int movie)<\/code>&nbsp;Returns a list of shops that have an&nbsp;<strong>unrented copy<\/strong>&nbsp;of the given&nbsp;<code>movie<\/code>&nbsp;as described above.<\/li><li><code>void rent(int shop, int movie)<\/code>&nbsp;Rents the given&nbsp;<code>movie<\/code>&nbsp;from the given&nbsp;<code>shop<\/code>.<\/li><li><code>void drop(int shop, int movie)<\/code>&nbsp;Drops off a previously rented&nbsp;<code>movie<\/code>&nbsp;at the given&nbsp;<code>shop<\/code>.<\/li><li><code>List&lt;List&lt;Integer&gt;&gt; report()<\/code>&nbsp;Returns a list of cheapest&nbsp;<strong>rented<\/strong>&nbsp;movies as described above.<\/li><\/ul>\n\n\n\n<p><strong>Note:<\/strong>&nbsp;The test cases will be generated such that&nbsp;<code>rent<\/code>&nbsp;will only be called if the shop has an&nbsp;<strong>unrented<\/strong>&nbsp;copy of the movie, and&nbsp;<code>drop<\/code>&nbsp;will only be called if the shop had&nbsp;<strong>previously rented<\/strong>&nbsp;out the movie.<\/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>\n[\"MovieRentingSystem\", \"search\", \"rent\", \"rent\", \"report\", \"drop\", \"search\"]\n[[3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]]], [1], [0, 1], [1, 2], [], [1, 2], [2]]\n<strong>Output<\/strong>\n[null, [1, 0, 2], null, null, [[0, 1], [1, 2]], null, [0, 1]]\n\n<strong>Explanation<\/strong>\nMovieRentingSystem movieRentingSystem = new MovieRentingSystem(3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]]);\nmovieRentingSystem.search(1);  \/\/ return [1, 0, 2], Movies of ID 1 are unrented at shops 1, 0, and 2. Shop 1 is cheapest; shop 0 and 2 are the same price, so order by shop number.\nmovieRentingSystem.rent(0, 1); \/\/ Rent movie 1 from shop 0. Unrented movies at shop 0 are now [2,3].\nmovieRentingSystem.rent(1, 2); \/\/ Rent movie 2 from shop 1. Unrented movies at shop 1 are now [1].\nmovieRentingSystem.report();   \/\/ return [[0, 1], [1, 2]]. Movie 1 from shop 0 is cheapest, followed by movie 2 from shop 1.\nmovieRentingSystem.drop(1, 2); \/\/ Drop off movie 2 at shop 1. Unrented movies at shop 1 are now [1,2].\nmovieRentingSystem.search(2);  \/\/ return [0, 1]. Movies of ID 2 are unrented at shops 0 and 1. Shop 0 is cheapest, followed by shop 1.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= n &lt;= 3 * 10<sup>5<\/sup><\/code><\/li><li><code>1 &lt;= entries.length &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>0 &lt;= shop<sub>i<\/sub>&nbsp;&lt; n<\/code><\/li><li><code>1 &lt;= movie<sub>i<\/sub>, price<sub>i<\/sub>&nbsp;&lt;= 10<sup>4<\/sup><\/code><\/li><li>Each shop carries&nbsp;<strong>at most one<\/strong>&nbsp;copy of a movie&nbsp;<code>movie<sub>i<\/sub><\/code>.<\/li><li>At most&nbsp;<code>10<sup>5<\/sup><\/code>&nbsp;calls&nbsp;<strong>in total<\/strong>&nbsp;will be made to&nbsp;<code>search<\/code>,&nbsp;<code>rent<\/code>,&nbsp;<code>drop<\/code>&nbsp;and&nbsp;<code>report<\/code>.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Hashtable + TreeSet<\/strong><\/h2>\n\n\n\n<p>We need three containers:<br>1. <strong><em>movies<\/em><\/strong> tracks the {movie -&gt; price} of each shop. This is readonly to get the price of a movie for generating keys for treesets.<br>2. <strong><em>unrented<\/em><\/strong> tracks unrented movies keyed by movie id,  value is a treeset ordered by {price, shop}.<br>3. <strong><em>rented<\/em><\/strong> tracks rented movies, a treeset <meta charset=\"utf-8\">ordered by {price, shop, movie}<\/p>\n\n\n\n<p>Note: By using array&lt;int, 3&gt; we can unpack values like below:<br>array&lt;int, 3&gt; entries; \/\/ {price, shop, movie}<br>for (const auto [price, shop, moive] : entries)<br>  &#8230;<\/p>\n\n\n\n<p>Time complexity: <br>Init: O(nlogn)<br>rent \/ drop: O(logn)<br>search \/ report: O(1)<\/p>\n\n\n\n<p>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 MovieRentingSystem {\npublic:\n  MovieRentingSystem(int n, vector<vector<int>>& entries): movies(n) {\n    for (const auto& e : entries) {\n      const int shop = e[0];\n      const int movie = e[1];\n      const int price = e[2];\n      movies[shop].emplace(movie, price);\n      unrented[movie].emplace(price, shop);\n    }\n  }\n\n  vector<int> search(int movie) {\n    vector<int> shops;\n    for (const auto [price, shop] : unrented[movie]) {\n      shops.push_back(shop);\n      if (shops.size() == 5) break;\n    }\n    return shops;\n  }\n\n  void rent(int shop, int movie) {\n    const int price = movies[shop][movie];\n    unrented[movie].erase({price, shop});\n    rented.insert({price, shop, movie});\n  }\n\n  void drop(int shop, int movie) {\n    const int price = movies[shop][movie];\n    rented.erase({price, shop, movie});\n    unrented[movie].emplace(price, shop);\n  }\n\n  vector<vector<int>> report() {\n    vector<vector<int>> ans;\n    for (const auto& [price, shop, movie] : rented) {\n      ans.push_back({shop, movie});\n      if (ans.size() == 5) break;\n    }\n    return ans;\n  }\nprivate:\n  vector<unordered_map<int, int>> movies; \/\/ shop -> {movie -> price}\n  unordered_map<int, set<pair<int, int>>> unrented; \/\/ movie -> {price, shop}\n  set<array<int, 3>> rented; \/\/ {price, shop, movie}\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You have a movie renting company consisting of&nbsp;n&nbsp;shops. You want to implement a renting system that supports searching for, booking, and returning movies. The system&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[89],"tags":[251,217,82,656],"class_list":["post-9387","post","type-post","status-publish","format-standard","hentry","category-data-structure","tag-design","tag-hard","tag-hashtable","tag-treeset","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9387","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=9387"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9387\/revisions"}],"predecessor-version":[{"id":9392,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9387\/revisions\/9392"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9387"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9387"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9387"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}