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:
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.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 * 1051 <= entries.length <= 1050 <= shopi < n1 <= moviei, pricei <= 104moviei.105 calls in total will be made to search, rent, drop and report.This approach utilizes hash maps to store the details of available movies per shop and uses a sorted list to efficiently manage and sort rented movies. We will use a map to keep track of unrented movies per movie ID with the shop details, and a separate sorted list to maintain the currently rented movies for easy sorting and reporting.
The solution uses the SortedList from sortedcontainers in Python to maintain the rented movies in a sorted order based on price, shop, and movie IDs. The available movies are stored in a dictionary with movie IDs as keys and a SortedList to keep shop prices ordered for efficient searching and renting operations.
Java
Time Complexity: O(log n) for rent and drop, O(1) for search and report. Space Complexity: O(m + r) where m is the number of movies and r is the number of rented records.
This approach leverages priority queues to efficiently manage the ordering of movies by price. For managing rented movies, a priority queue is used alongside a hash set to quickly verify current rentals. This structure facilitates rapid data retrieval and updates when executing search and report operations.
The C++ solution employs unordered maps to track available movies and their details, while priority queues maintain the sorted order for both available and rented movies. This setup allows efficient access to the top entries for search and report operations, leveraging the hash set to verify current rentals efficiently.
JavaScript
Time Complexity: O(log n) for rent, drop, and report with heap operations. Space Complexity: O(m + r) where m is the count of unrented entries and r is rented entries.
| Approach | Complexity |
|---|---|
| Using HashMap and SortedList | Time Complexity: O(log n) for |
| Using Priority Queues and HashSet | Time Complexity: O(log n) for |
50 hours of Mid-Level System Design in One Hour • Raymond Jones • 105,950 views views
Watch 9 more video solutions →Practice Design Movie Rental System with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor