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`

indicates that there is a copy of movie _{i}, movie_{i}, price_{i}]`movie`

at shop _{i}`shop`

with a rental price of _{i}`price`

. Each shop carries _{i}**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`

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._{i}**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`

where`res[j] = [shop`

describes that the_{j}, movie_{j}]`j`

cheapest rented movie^{th}`movie`

was rented from the shop_{j}`shop`

. The movies in_{j}`res`

should be sorted by**price**in ascending order, and in case of a tie, the one with the**smaller**`shop`

should appear first, and if there is still tie, the one with the_{j}**smaller**`movie`

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._{j}

Implement the `MovieRentingSystem`

class:

`MovieRentingSystem(int n, int[][] entries)`

Initializes the`MovieRentingSystem`

object with`n`

shops and the movies in`entries`

.`List<Integer> search(int movie)`

Returns a list of shops that have an**unrented copy**of the given`movie`

as described above.`void rent(int shop, int movie)`

Rents the given`movie`

from the given`shop`

.`void drop(int shop, int movie)`

Drops off a previously rented`movie`

at the given`shop`

.`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]]ExplanationMovieRentingSystem 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`

calls^{5}**in total**will be made to`search`

,`rent`

,`drop`

and`report`

.

**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`

.

```
// OJ: https://leetcode.com/problems/design-movie-rental-system/
// 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;
}
};
```