Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1912.html
1912. Design Movie Rental System (Hard)
You have a movie renting company consisting of n
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.
Each movie is given as a 2D integer array entries
where entries[i] = [shop_{i}, movie_{i}, price_{i}]
indicates that there is a copy of movie movie_{i}
at shop shop_{i}
with a rental price of price_{i}
. Each shop carries at most one copy of a movie movie_{i}
.
The system should support the following functions:
 Search: Finds the cheapest 5 shops that have an unrented copy of a given movie. The shops should be sorted by price in ascending order, and in case of a tie, the one with the smaller
shop_{i}
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.  Rent: Rents an unrented copy of a given movie from a given shop.
 Drop: Drops off a previously rented copy of a given movie at a given shop.
 Report: Returns the cheapest 5 rented movies (possibly of the same movie ID) as a 2D list
res
whereres[j] = [shop_{j}, movie_{j}]
describes that thej^{th}
cheapest rented moviemovie_{j}
was rented from the shopshop_{j}
. The movies inres
should be sorted by price in ascending order, and in case of a tie, the one with the smallershop_{j}
should appear first, and if there is still tie, the one with the smallermovie_{j}
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.
Implement the MovieRentingSystem
class:
MovieRentingSystem(int n, int[][] entries)
Initializes theMovieRentingSystem
object withn
shops and the movies inentries
.List<Integer> search(int movie)
Returns a list of shops that have an unrented copy of the givenmovie
as described above.void rent(int shop, int movie)
Rents the givenmovie
from the givenshop
.void drop(int shop, int movie)
Drops off a previously rentedmovie
at the givenshop
.List<List<Integer>> report()
Returns a list of cheapest rented movies as described above.
Note: The test cases will be generated such that rent
will only be called if the shop has an unrented copy of the movie, and drop
will only be called if the shop had previously rented out the movie.
Example 1:
Input ["MovieRentingSystem", "search", "rent", "rent", "report", "drop", "search"] [[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]] Output [null, [1, 0, 2], null, null, [[0, 1], [1, 2]], null, [0, 1]] Explanation MovieRentingSystem movieRentingSystem = new MovieRentingSystem(3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]]); movieRentingSystem.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. movieRentingSystem.rent(0, 1); // Rent movie 1 from shop 0. Unrented movies at shop 0 are now [2,3]. movieRentingSystem.rent(1, 2); // Rent movie 2 from shop 1. Unrented movies at shop 1 are now [1]. movieRentingSystem.report(); // return [[0, 1], [1, 2]]. Movie 1 from shop 0 is cheapest, followed by movie 2 from shop 1. movieRentingSystem.drop(1, 2); // Drop off movie 2 at shop 1. Unrented movies at shop 1 are now [1,2]. movieRentingSystem.search(2); // return [0, 1]. Movies of ID 2 are unrented at shops 0 and 1. Shop 0 is cheapest, followed by shop 1.
Constraints:
1 <= n <= 3 * 10^{5}
1 <= entries.length <= 10^{5}
0 <= shop_{i} < n
1 <= movie_{i}, price_{i} <= 10^{4}
 Each shop carries at most one copy of a movie
movie_{i}
.  At most
10^{5}
calls in total will be made tosearch
,rent
,drop
andreport
.
Companies:
Flipkart
Related Topics:
Heap, Design, Ordered Map
Solution 1.
Intuition: Since search
is reporting unrented
movies while report
is reporting rented
movies, we can use two data structures to store unrented
and rented
movies, and rent
and drop
just moves the entry between these two data structures.
Algorithm:
search
: for a specific movie
, we need the cheapest 5 {price, shop}
pairs. So we can use unordered_map<Movie, set<pair<Price, Shop>>>
for unrented
(movie > set of {price, shop}
) so that we can simply return the first 5 shops in the set of unrented[movie]
.
report
: we need the cheapest 5 {price, shop, movie}
tuple. So we can use set<tuple<Price, Shop, Movie>>
for rented
so that we can simply return the first 5 {shop, movie}
pairs in the rented
set.
rent
: Given shop, movie
, we need to move this entry from unrented
to rented
. We need a separate map map<pair<Shop, Movie>, Price> price
({shop, movie} > price
) to query the price given pair {shop, movie}
. Then we just need to unrented[movie].erase({price, shop})
and rented.emplace(price, shop, movie)
.
drop
: Similar to rent
, we first get the corresponding price
then move the entry from rented
to unrented
.

import java.util.*; class MovieRentingSystem { private Map<Integer, Set<int[]>> available; // Available movies and their rental price private Map<String, Map<Integer, Integer>> rented; // Rented movies, customer ID and rental price private PriorityQueue<int[]> cheapest; // Cheapest k rented movies public MovieRentingSystem(int n, int[][] entries) { available = new HashMap<>(); rented = new HashMap<>(); cheapest = new PriorityQueue<>((a, b) > a[2] == b[2] ? a[0]  b[0] : a[2]  b[2]); for (int[] entry : entries) { int movie = entry[0]; int shop = entry[1]; int price = entry[2]; available.computeIfAbsent(movie, k > new HashSet<>()).add(new int[] {shop, price}); } } public List<Integer> search(int movie) { List<Integer> res = new ArrayList<>(); if (available.containsKey(movie)) { for (int[] shopPrice : available.get(movie)) { res.add(shopPrice[0]); } } return res; } public void rent(int movie, int shop, int userId) { int[] rent = new int[] {movie, shop, available.get(movie).stream().filter(sp > sp[0] == shop).findFirst().get()[1]}; cheapest.offer(rent); available.get(movie).remove(rent); rented.computeIfAbsent(userId + "", k > new HashMap<>()).put(movie, rent[2]); } public void drop(int movie, int shop, int userId) { int price = rented.get(userId + "").remove(movie); available.computeIfAbsent(movie, k > new HashSet<>()).add(new int[] {shop, price}); cheapest.removeIf(rent > rent[0] == movie && rent[1] == shop); } public List<List<Integer>> report() { List<List<Integer>> res = new ArrayList<>(); while (res.size() < 5 && !cheapest.isEmpty()) { int[] rent = cheapest.poll(); int movie = rent[0], shop = rent[1], price = rent[2]; res.add(Arrays.asList(movie, shop)); rented.get(getCustomer(rent)).put(movie, price); } return res; } private String getCustomer(int[] rent) { int movie = rent[0], shop = rent[1]; for (Map.Entry<String, Map<Integer, Integer>> entry : rented.entrySet()) { if (entry.getValue().containsKey(movie) && entry.getValue().get(movie) == rent[2]) { return entry.getKey(); } } return null; } }

// OJ: https://leetcode.com/problems/designmovierentalsystem/ // Time: // MovieRentingSystem: O(ElogE) // search: O(1) // rent: O(logE) // drop: O(logE) // report: O(1) // Space: O(E) class MovieRentingSystem { map<pair<int, int>, int> price; // {shop, movie} > price unordered_map<int, set<pair<int, int>>> unrented; // movie > set of {price, shop} set<tuple<int, int, int>> rented; // set of {price, shop, movie} public: MovieRentingSystem(int n, vector<vector<int>>& entries) { for (auto &e : entries) {// shop, movie, price int shop = e[0], movie = e[1], p = e[2]; price[{shop, movie}] = p; unrented[movie].emplace(p, shop); } } vector<int> search(int movie) { auto &s = unrented[movie]; vector<int> ans; int i = 0; for (auto it = s.begin(); i < 5 && it != s.end(); ++it, ++i) { ans.push_back(it>second); } return ans; } void rent(int shop, int movie) { int p = price[{shop, movie}]; unrented[movie].erase({p, shop}); rented.emplace(p, shop, movie); } void drop(int shop, int movie) { int p = price[{shop, movie}]; rented.erase({p, shop, movie}); unrented[movie].emplace(p, shop); } vector<vector<int>> report() {// shop, movie vector<vector<int>> ans; int i = 0; for (auto it = rented.begin(); it != rented.end() && i < 5; ++i, ++it) { auto [p, s, m] = *it; ans.push_back({s, m}); } return ans; } };

from collections import defaultdict class MovieRentingSystem: def __init__(self, n: int, entries: List[List[int]]): self.movie_to_shop_price = defaultdict(list) self.shop_to_movie_price = defaultdict(dict) self.rented = set() for shop, movie, price in entries: self.movie_to_shop_price[movie].append((price, shop)) self.shop_to_movie_price[shop][movie] = price def search(self, movie: int) > List[int]: return [shop for price, shop in sorted(self.movie_to_shop_price[movie])[:5]] def rent(self, shop: int, movie: int) > None: price = self.shop_to_movie_price[shop][movie] self.rented.add((movie, shop, price)) self.movie_to_shop_price[movie].remove((price, shop)) def drop(self, shop: int, movie: int) > None: price = self.shop_to_movie_price[shop][movie] self.rented.remove((movie, shop, price)) self.movie_to_shop_price[movie].append((price, shop)) def report(self) > List[List[int]]: return [[movie, shop] for movie, shop, price in sorted(self.rented, key=lambda x: (x[2], x[1], x[0]))[:5]]