Page Contents

*Design Movie Rental System Solution*

*Design Movie Rental System Solution*

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`

.

**SOLUTION**

*Below is the explanation on the data structures:*

```
Map<String, Entry> entryMap = new HashMap<>();
Map<Integer, TreeSet<Entry>> available = new HashMap<>();
Set<Entry> rented = new HashSet<>();
```

- entryMap, is request to get the objects by a (shop & movie) combination in O(1). Because those are unique.
- available, is required to get the available movies while serching, and Since those are already shorted, search will also be constant time. O(5) ~= O(1)
- rented, is required to maintain the entries those are rented so that it can be used while the report call. This will be a O(N Log N), where N is items those are sold.
- By converting this to a TreeSet, we can reduce the report Time complexity to constant.

*Program:**Design Movie Rental System Solution in Java*

```
class MovieRentingSystem {
int n, limit = 5;
Map<String, Entry> entryMap = new HashMap<>();
Map<Integer, TreeSet<Entry>> available = new HashMap<>();
Comparator<Entry> order = (e1, e2) -> e1.price == e2.price ? (e1.shop == e2.shop ? Integer.compare(e1.movie, e2.movie) : Integer.compare(e1.shop, e2.shop)) : Integer.compare(e1.price, e2.price);
// TreeSet<Entry> rented = new TreeSet<>(order);
Set<Entry> rented = new HashSet<>();
public MovieRentingSystem(int n, int[][] entries) {
this.n = n;
for (int[] entry : entries) {
Entry entryObj = new Entry(entry[0], entry[1], entry[2]);
entryMap.put(getKey(entryObj), entryObj);
addAvailability(entryObj);
}
}
void addAvailability(Entry entry) {
available.computeIfAbsent(entry.movie, val -> new TreeSet<>(order)).add(entry);
}
String getKey(Entry entry) {
return getKey(entry.shop, entry.movie);
}
String getKey(int shop, int movie) {
return shop + " -> " + movie;
}
public List<Integer> search(int movie) {
return available.getOrDefault(movie, new TreeSet<>(order)).stream().limit(limit).map(entry -> entry.shop).collect(Collectors.toList());
}
// Time: Log m, where m is number of available Entries for the movie, because we are removing it from available sorted set.
public void rent(int shop, int movie) {
Entry entry = entryMap.get(getKey(shop, movie));
if (entry == null) return;
available.get(movie).remove(entry);
rented.add(entry);
}
// Time: Log m, where m is number of available Entries for the movie, because we are adding it to available sorted set.
public void drop(int shop, int movie) {
Entry entry = entryMap.get(getKey(shop, movie));
if (entry == null) return;
rented.remove(entry);
addAvailability(entry);
}
public List<List<Integer>> report() {
// Loop though all the rented items and sort those by the order, and limit only 5.
return rented.stream().sorted(order).limit(limit).map(entry -> List.of(entry.shop, entry.movie)).collect(Collectors.toList());
}
class Entry {
int shop, movie, price;
Entry(int shop, int movie, int price) {
this.shop = shop;
this.movie = movie;
this.price = price;
}
}
}
```

*Credit : Here*

*Weekly Contest 247*

*Weekly Contest 247*

*Maximum Product Difference Between Two Pairs**Cyclically Rotating a Grid**Number of Wonderful Substrings**Count Ways to Build Rooms in an Ant Colony*

*Biweekly Contest 55*

*Biweekly Contest 55*

*Remove One Element to Make the Array Strictly Increasing**Remove All Occurrences of a Substring**Maximum Alternating Subsequence Sum**Design Movie Rental System*