Design Movie Rental System — LeetCode 1912 Python Solution
HardDesignArrayHash TableOrdered SetHeap (Priority Queue)
- Problem
- #1912
- Pattern
- Heap / Priority Queue
- Reading time
- 7 min
- Source
- leetcode.com
The 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.
Example
- Input
- ["MovieRentingSystem", "search", "rent", "rent", "report", "drop", "search"]
- 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]]);
Python solution
Python
class MovieRentingSystem:
def __init__(self, n: int, entries: List[List[int]]):
self.available = defaultdict(lambda: SortedList())
self.price_map = {}
for shop, movie, price in entries:
self.available[movie].add((price, shop))
self.price_map[self.f(shop, movie)] = price
self.rented = SortedList()
def search(self, movie: int) -> List[int]:
return [shop for _, shop in self.available[movie][:5]]
def rent(self, shop: int, movie: int) -> None:
price = self.price_map[self.f(shop, movie)]
self.available[movie].remove((price, shop))
self.rented.add((price, shop, movie))
def drop(self, shop: int, movie: int) -> None:
price = self.price_map[self.f(shop, movie)]
self.rented.remove((price, shop, movie))
self.available[movie].add((price, shop))
def report(self) -> List[List[int]]:
return [[shop, movie] for _, shop, movie in self.rented[:5]]
def f(self, shop: int, movie: int) -> int:
return shop << 30 | movie
# Your MovieRentingSystem object will be instantiated and called as such:
# obj = MovieRentingSystem(n, entries)
# param_1 = obj.search(movie)
# obj.rent(shop,movie)
# obj.drop(shop,movie)
# param_4 = obj.report()Complexity
| Measure | Complexity |
|---|---|
| Time | O(m \log m), where m is the length of \text{entries} |
| Space | O(m), where m is the length of \text{entries} auxiliary |
Pattern: Heap / Priority Queue
Keep only the best k elements, or always pull the smallest, in log time. LeetCode 1912. Design Movie Rental System is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.
The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 1912. Design Movie Rental System?
- LeetCode 1912. Design Movie Rental System is rated Hard on LeetCode.
- What is the time complexity of LeetCode 1912. Design Movie Rental System?
- The Python solution on this page runs in O(m \log m), where m is the length of \text{entries}.
- What is the space complexity of LeetCode 1912. Design Movie Rental System?
- The Python solution on this page uses O(m), where m is the length of \text{entries} auxiliary space.
- What topics does LeetCode 1912. Design Movie Rental System cover?
- LeetCode 1912. Design Movie Rental System is tagged Design, Array, Hash Table, Ordered Set and Heap (Priority Queue) on LeetCode.