# Design Movie Rental System
**Difficulty:** HARD
[External](https://leetcode.com/problems/design-movie-rental-system)
Canonical: https://scaleengineer.com/dsa/problems/design-movie-rental-system
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Data structures:** Array, Hash Table, Heap (Priority Queue), Ordered Set
**Companies:** [Flipkart](https://scaleengineer.com/companies/flipkart)
---
## Problem
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] = [shopi, moviei, pricei]` indicates that there is a copy of movie `moviei` at shop `shopi` with a rental price of `pricei`. Each shop carries **at most one** copy of a movie `moviei`.

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** `shopi` 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` where `res[j] = [shopj, moviej]` describes that the `jth` cheapest rented movie `moviej` was rented from the shop `shopj`. The movies in `res` should be sorted by **price** in ascending order, and in case of a tie, the one with the **smaller** `shopj` should appear first, and if there is still tie, the one with the **smaller** `moviej` 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 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]]

**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 * 105`
* `1 <= entries.length <= 105`
* `0 <= shopi < n`
* `1 <= moviei, pricei <= 104`
* Each shop carries **at most one** copy of a movie `moviei`.
* At most `105` calls **in total** will be made to `search`, `rent`, `drop` and `report`.

# Approaches
## Brute-Force with On-Demand Sorting
This approach uses basic data structures and performs sorting on-demand. We maintain a list of all possible movie rentals and a set to track which ones are currently rented. When a search or report is requested, we iterate through the relevant movies, filter them, sort them according to the specified criteria, and then return the top 5 results. While simple to implement, this method is inefficient for large datasets or frequent calls to `search` and `report`.
**Time:** *   **Constructor**: O(E)
*   **search**: O(U + K log K), where U is the total number of unrented movies and K is the number of unrented copies of the specific movie. In the worst case, this is O(E + n log n).
*   **rent**: O(1) on average.
*   **drop**: O(1) on average.
*   **report**: O(R log R), where R is the number of rented movies. In the worst case, this is O(E log E). · **Space:** O(E), where E is the number of entries. This is for storing all movie data and their rental status.
**Pros:** Simple to understand and implement.; The `rent` and `drop` operations are very fast, with an average time complexity of O(1).
**Cons:** The `search` operation is very slow as it requires iterating through all movie entries in the system.; The `report` operation is inefficient because it involves collecting all rented movies and sorting them every time, which can be costly if there are many rented movies.
### Explanation
In this brute-force method, we don't pre-process the data for efficient querying. We store the movie prices in a map for quick lookup and use a set to keep track of rented movies. 

For a `search` query, we must scan through all movie entries, check if they match the target movie and are unrented, collect them, and then perform a sort. Similarly, for a `report`, we collect all rented movies, look up their prices, and sort the entire collection. This leads to high time complexity for these operations, especially when the number of movies or rented items is large.

```java
class MovieRentingSystem {
    // Map to store price: key is a unique long for (shop, movie), value is price
    private Map<Long, Integer> prices;
    // Set of all unrented movies, identified by a unique long for (shop, movie)
    private Set<Long> unrented;
    // Set of all rented movies, identified by a unique long for (shop, movie)
    private Set<Long> rented;
    // A constant for encoding/decoding (shop, movie) pairs into a long
    private static final int MOVIE_ID_FACTOR = 10001;

    public MovieRentingSystem(int n, int[][] entries) {
        prices = new HashMap<>();
        unrented = new HashSet<>();
        rented = new HashSet<>();

        for (int[] entry : entries) {
            int shop = entry[0], movie = entry[1], price = entry[2];
            long key = (long) shop * MOVIE_ID_FACTOR + movie;
            prices.put(key, price);
            unrented.add(key);
        }
    }

    public List<Integer> search(int movie) {
        List<int[]> candidates = new ArrayList<>();
        for (long key : unrented) {
            int currentMovie = (int) (key % MOVIE_ID_FACTOR);
            if (currentMovie == movie) {
                int shop = (int) (key / MOVIE_ID_FACTOR);
                int price = prices.get(key);
                candidates.add(new int[]{price, shop});
            }
        }
        candidates.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < Math.min(5, candidates.size()); i++) {
            result.add(candidates.get(i)[1]);
        }
        return result;
    }

    public void rent(int shop, int movie) {
        long key = (long) shop * MOVIE_ID_FACTOR + movie;
        unrented.remove(key);
        rented.add(key);
    }

    public void drop(int shop, int movie) {
        long key = (long) shop * MOVIE_ID_FACTOR + movie;
        rented.remove(key);
        unrented.add(key);
    }

    public List<List<Integer>> report() {
        List<int[]> rentedList = new ArrayList<>();
        for (long key : rented) {
            int shop = (int) (key / MOVIE_ID_FACTOR);
            int movie = (int) (key % MOVIE_ID_FACTOR);
            int price = prices.get(key);
            rentedList.add(new int[]{price, shop, movie});
        }
        rentedList.sort((a, b) -> {
            if (a[0] != b[0]) return a[0] - b[0];
            if (a[1] != b[1]) return a[1] - b[1];
            return a[2] - b[2];
        });
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < Math.min(5, rentedList.size()); i++) {
            result.add(List.of(rentedList.get(i)[1], rentedList.get(i)[2]));
        }
        return result;
    }
}
```
### Algorithm
*   **Initialization (`MovieRentingSystem`)**: 
    *   Store all movie entries in a list or map for easy access to their properties (shop, movie, price).
    *   Use a `Set` to keep track of which movies are currently rented. An entry in the set can be a pair of `(shop, movie)`.
*   **Search (`search(movie)`)**: 
    *   Iterate through all movie entries in the system.
    *   For each entry, check if it matches the given `movie` ID and if it's not in the `rented` set.
    *   Collect all such unrented movies into a temporary list.
    *   Sort this list based on price (ascending) and then shop ID (ascending).
    *   Return the shop IDs of the top 5 movies from the sorted list.
*   **Rent (`rent(shop, movie)`)**: 
    *   Add the pair `(shop, movie)` to the `rented` set.
*   **Drop (`drop(shop, movie)`)**: 
    *   Remove the pair `(shop, movie)` from the `rented` set.
*   **Report (`report()`)**: 
    *   Create a temporary list of all rented movies.
    *   Iterate through the `rented` set. For each `(shop, movie)` pair, find its price.
    *   Add the tuple `(price, shop, movie)` to the temporary list.
    *   Sort this list based on price (ascending), then shop ID (ascending), and finally movie ID (ascending).
    *   Return the `(shop, movie)` pairs of the top 5 entries from the sorted list.

## HashMap and Heap/Sorting
This approach improves upon the brute-force method by organizing the data more effectively. We group unrented movies by their ID, which speeds up the `search` operation as we no longer need to scan all movies. For the `report` operation, instead of sorting all rented movies, we can use a max-heap of size 5 to find the 5 cheapest ones in linear time with respect to the number of rented movies. This is more efficient than a full sort, but still requires iterating over all rented items.
**Time:** *   **Constructor**: O(E)
*   **search**: O(K log K), where K is the number of shops with the movie (K <= n).
*   **rent**: O(1) on average.
*   **drop**: O(1) on average.
*   **report**: O(R), where R is the number of rented movies (R <= E). · **Space:** O(E), where E is the number of entries, for storing prices and movie locations.
**Pros:** Faster `search` than the brute-force approach by grouping movies by ID.; Faster `report` than sorting all rented movies by using a heap.; `rent` and `drop` operations remain very fast at O(1) average time.
**Cons:** The `search` operation still requires sorting, which can be slow if a movie is available in many shops (O(K log K), where K is the number of shops).; The `report` operation, while better than a full sort, still needs to iterate through all rented movies (O(R), where R is the number of rented movies).
### Explanation
This intermediate solution uses HashMaps to structure the data for faster lookups. Unrented movies are grouped by movie ID, allowing `search` to only consider shops that actually have the movie. This avoids a full scan of all system entries.

For `report`, we optimize by using a max-priority queue (max-heap) of a fixed size (5). As we iterate through the rented movies, we maintain the 5 cheapest movies seen so far in the heap. This is more efficient than sorting the entire list of rented movies, reducing the complexity from O(R log R) to O(R log 5), which is effectively O(R).

```java
class MovieRentingSystem {
    private Map<Integer, Map<Integer, Integer>> prices; // shop -> movie -> price
    private Map<Integer, Set<Integer>> unrentedByMovie; // movie -> set of shops
    private Set<Long> rented;
    private static final int MOVIE_ID_FACTOR = 10001;

    public MovieRentingSystem(int n, int[][] entries) {
        prices = new HashMap<>();
        unrentedByMovie = new HashMap<>();
        rented = new HashSet<>();

        for (int[] entry : entries) {
            int shop = entry[0], movie = entry[1], price = entry[2];
            prices.computeIfAbsent(shop, k -> new HashMap<>()).put(movie, price);
            unrentedByMovie.computeIfAbsent(movie, k -> new HashSet<>()).add(shop);
        }
    }

    public List<Integer> search(int movie) {
        if (!unrentedByMovie.containsKey(movie)) {
            return new ArrayList<>();
        }
        List<int[]> candidates = new ArrayList<>();
        for (int shop : unrentedByMovie.get(movie)) {
            int price = prices.get(shop).get(movie);
            candidates.add(new int[]{price, shop});
        }
        candidates.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < Math.min(5, candidates.size()); i++) {
            result.add(candidates.get(i)[1]);
        }
        return result;
    }

    public void rent(int shop, int movie) {
        unrentedByMovie.get(movie).remove(shop);
        rented.add((long) shop * MOVIE_ID_FACTOR + movie);
    }

    public void drop(int shop, int movie) {
        rented.remove((long) shop * MOVIE_ID_FACTOR + movie);
        unrentedByMovie.get(movie).add(shop);
    }

    public List<List<Integer>> report() {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
            if (b[0] != a[0]) return b[0] - a[0];
            if (b[1] != a[1]) return b[1] - a[1];
            return b[2] - a[2];
        });

        for (long key : rented) {
            int shop = (int) (key / MOVIE_ID_FACTOR);
            int movie = (int) (key % MOVIE_ID_FACTOR);
            int price = prices.get(shop).get(movie);
            pq.offer(new int[]{price, shop, movie});
            if (pq.size() > 5) {
                pq.poll();
            }
        }

        List<List<Integer>> result = new ArrayList<>();
        while (!pq.isEmpty()) {
            int[] entry = pq.poll();
            result.add(List.of(entry[1], entry[2]));
        }
        Collections.reverse(result);
        return result;
    }
}
```
### Algorithm
*   **Initialization (`MovieRentingSystem`)**: 
    *   Use a `Map<Integer, Map<Integer, Integer>>` to store prices: `shop -> movie -> price`.
    *   Use a `Map<Integer, Set<Integer>>` to store unrented movies, mapping a `movie` ID to a `Set` of `shop` IDs that have it.
    *   Use a `Set` to store rented movies as `(shop, movie)` pairs.
*   **Search (`search(movie)`)**: 
    *   Retrieve the set of shops for the given `movie` from the unrented movies map.
    *   For each shop, look up its price.
    *   Collect these `(price, shop)` pairs into a list and sort it.
    *   Return the top 5 shops.
*   **Rent (`rent(shop, movie)`)**: 
    *   Remove the `shop` from the set of available shops for the given `movie`.
    *   Add the `(shop, movie)` pair to the `rented` set.
*   **Drop (`drop(shop, movie)`)**: 
    *   Remove the `(shop, movie)` pair from the `rented` set.
    *   Add the `shop` back to the set of available shops for the given `movie`.
*   **Report (`report()`)**: 
    *   Iterate through the `rented` set.
    *   For each rented movie, find its price.
    *   Use a max-heap of size 5 to keep track of the 5 cheapest rented movies found so far. This avoids a full sort.
    *   Extract the movies from the heap, sort them, and return the result.

## HashMap and TreeSet (Balanced BST)
This is the most efficient approach, utilizing balanced binary search trees (implemented as `TreeSet` in Java) to maintain sorted collections of movies. By keeping the unrented and rented movies sorted at all times, the `search` and `report` operations become extremely fast. They simply need to read the first few elements from the pre-sorted data structures. The trade-off is that the `rent` and `drop` operations, which modify these structures, take logarithmic time instead of constant time. Given the problem constraints, this approach provides the best overall performance.
**Time:** *   **Constructor**: O(E * log n), where E is entries and n is shops. The log factor comes from adding to a TreeSet which can have up to n elements for a single movie.
*   **search**: O(1), technically O(log n) for map lookup + O(5) for iteration, but map lookup is amortized O(1).
*   **rent**: O(log n + log E). O(log n) to remove from an unrented set and O(log E) to add to the rented set.
*   **drop**: O(log E + log n). O(log E) to remove from the rented set and O(log n) to add to an unrented set.
*   **report**: O(1), as we just iterate through the first 5 elements of the sorted set. · **Space:** O(E), where E is the number of entries, to store all movie data in the maps and TreeSets.
**Pros:** Extremely fast `search` and `report` operations, effectively O(1) as they only need the first 5 elements.; Guarantees the best performance for a high volume of search and report queries.
**Cons:** The implementation is more complex due to the use of custom comparators for the TreeSets.; The `rent` and `drop` operations are slightly slower (logarithmic time) compared to the O(1) of the HashMap approach, but this is a good trade-off for the massive speedup in `search` and `report`.
### Explanation
The core idea is to maintain the required sorted order of movies at all times, so that `search` and `report` queries are answered instantly. We use `TreeSet`, a data structure based on a balanced binary search tree, to achieve this.

1.  `unrentedMovies`: A `Map` from a movie ID to a `TreeSet`. Each `TreeSet` stores pairs of `{price, shop}` for a specific movie and keeps them sorted by price, then shop. This allows `search` to retrieve the top 5 cheapest shops in constant time (as we only need the first 5 elements).
2.  `rentedMovies`: A single `TreeSet` that stores all rented movies as `{price, shop, movie}` tuples. It's sorted by price, then shop, then movie. This allows `report` to get the top 5 cheapest rented movies instantly.

When a movie is rented or dropped, we perform `add` and `remove` operations on these `TreeSet`s, which take logarithmic time but ensure the collections remain sorted. This pre-computation of sorted order makes the query operations highly efficient.

```java
class MovieRentingSystem {
    // Map to store prices for quick lookup: shop -> movie -> price
    private Map<Integer, Map<Integer, Integer>> prices;
    // Map of unrented movies: movie -> sorted set of {price, shop}
    private Map<Integer, TreeSet<int[]>> unrentedMovies;
    // Sorted set of all rented movies: {price, shop, movie}
    private TreeSet<int[]> rentedMovies;

    public MovieRentingSystem(int n, int[][] entries) {
        prices = new HashMap<>();
        unrentedMovies = new HashMap<>();
        // Comparator for rented movies: sort by price, then shop, then movie
        rentedMovies = new TreeSet<>((a, b) -> {
            if (a[0] != b[0]) return a[0] - b[0];
            if (a[1] != b[1]) return a[1] - b[1];
            return a[2] - b[2];
        });

        for (int[] entry : entries) {
            int shop = entry[0], movie = entry[1], price = entry[2];
            prices.computeIfAbsent(shop, k -> new HashMap<>()).put(movie, price);
            // Comparator for unrented movies: sort by price, then shop
            unrentedMovies.computeIfAbsent(movie, k -> new TreeSet<>((a, b) -> {
                if (a[0] != b[0]) return a[0] - b[0];
                return a[1] - b[1];
            })).add(new int[]{price, shop});
        }
    }

    public List<Integer> search(int movie) {
        List<Integer> result = new ArrayList<>();
        if (!unrentedMovies.containsKey(movie)) {
            return result;
        }
        TreeSet<int[]> shops = unrentedMovies.get(movie);
        int count = 0;
        for (int[] shopInfo : shops) {
            if (count++ >= 5) break;
            result.add(shopInfo[1]);
        }
        return result;
    }

    public void rent(int shop, int movie) {
        int price = prices.get(shop).get(movie);
        unrentedMovies.get(movie).remove(new int[]{price, shop});
        rentedMovies.add(new int[]{price, shop, movie});
    }

    public void drop(int shop, int movie) {
        int price = prices.get(shop).get(movie);
        rentedMovies.remove(new int[]{price, shop, movie});
        unrentedMovies.get(movie).add(new int[]{price, shop});
    }

    public List<List<Integer>> report() {
        List<List<Integer>> result = new ArrayList<>();
        int count = 0;
        for (int[] movieInfo : rentedMovies) {
            if (count++ >= 5) break;
            result.add(List.of(movieInfo[1], movieInfo[2]));
        }
        return result;
    }
}
```
### Algorithm
*   **Initialization (`MovieRentingSystem`)**: 
    *   Use a `Map<Integer, Map<Integer, Integer>>` to store prices: `shop -> movie -> price`.
    *   Use a `Map<Integer, TreeSet<int[]>>` for unrented movies. The key is the `movie` ID, and the value is a `TreeSet` of `int[]{price, shop}`, automatically sorted by price then shop.
    *   Use a single `TreeSet<int[]>` for all rented movies. It stores `int[]{price, shop, movie}` and is sorted by price, then shop, then movie.
*   **Search (`search(movie)`)**: 
    *   Look up the `TreeSet` for the given `movie` in the unrented movies map.
    *   Iterate through the first 5 elements of the `TreeSet` and collect the shop IDs. Since the set is always sorted, this is very fast.
*   **Rent (`rent(shop, movie)`)**: 
    *   Look up the movie's price.
    *   Remove the `(price, shop)` entry from the corresponding `TreeSet` in the unrented map.
    *   Add a `(price, shop, movie)` entry to the global `TreeSet` of rented movies.
*   **Drop (`drop(shop, movie)`)**: 
    *   Look up the movie's price.
    *   Remove the `(price, shop, movie)` entry from the global `TreeSet` of rented movies.
    *   Add a `(price, shop)` entry back to the `TreeSet` in the unrented map.
*   **Report (`report()`)**: 
    *   Iterate through the first 5 elements of the global `TreeSet` of rented movies.
    *   Collect the `(shop, movie)` pairs and return them.

# Solutions
### Java

```java
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 ; } }
```

### Python

```python
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 ]]
```

### CPP

```cpp
// 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 ; } };
```