Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Sign up
Appearance settings

Commit e573bd5

Browse files
D. J.:
- Added the leetcode problem and solution for 1912
1 parent ee7f7ed commit e573bd5

File tree

3 files changed

+155
-0
lines changed

3 files changed

+155
-0
lines changed

‎README.md‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -286,6 +286,7 @@
286286
- [1534 Count Good Triplets](https://leetcode.com/problems/count-good-triplets/description/)
287287
- [1679 Max Number of K-Sum Pairs](https://leetcode.com/problems/max-number-of-k-sum-pairs/description/)
288288
- [1732 Find the Highest Altitude](https://leetcode.com/problems/find-the-highest-altitude/description/)
289+
- [1912 Design Movie Rental System](https://leetcode.com/problems/design-movie-rental-system/description/)
289290
- [1991 Find the Middle Index in Array](https://leetcode.com/problems/find-the-middle-index-in-array/description/)
290291
- [1922 Count Good Numbers](https://leetcode.com/problems/count-good-numbers/description/)
291292
- [1964 Find the Longest Valid Obstacle Course at Each Position](https://leetcode.com/problems/find-the-longest-valid-obstacle-course-at-each-position/description/)
Lines changed: 138 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,138 @@
1+
import collections
2+
import heapq
3+
from typing import List
4+
5+
6+
class MovieRentingSystem:
7+
"""
8+
You have a movie renting company consisting of n shops. You want to implement a
9+
renting system that supports searching for, booking, and returning movies. The
10+
system should also support generating a report of the currently rented movies.
11+
12+
Each movie is given as a 2D integer array entries where entries[i] =
13+
[shopi, moviei, pricei] indicates that there is a copy of movie moviei at shop
14+
shopi with a rental price of pricei. Each shop carries at most one copy of a movie
15+
moviei.
16+
17+
The system should support the following functions:
18+
- Search: Finds the cheapest 5 shops that have an unrented copy of a given movie.
19+
The shops should be sorted by price in ascending order, and in case of a tie, the
20+
one with the smaller shopi should appear first. If there are less than 5 matching
21+
shops, then all of them should be returned. If no shop has an unrented copy, then
22+
an empty list should be returned.
23+
- Rent: Rents an unrented copy of a given movie from a given shop.
24+
- Drop: Drops off a previously rented copy of a given movie at a given shop.
25+
- Report: Returns the cheapest 5 rented movies (possibly of the same movie ID) as a
26+
2D list res where res[j] = [shopj, moviej] describes that the jth cheapest rented
27+
movie moviej was rented from the shop shopj. The movies in res should be sorted by
28+
price in ascending order, and in case of a tie, the one with the smaller shopj
29+
should appear first, and if there is still tie, the one with the smaller moviej
30+
should appear first. If there are fewer than 5 rented movies, then all of them
31+
should be returned. If no movies are currently being rented, then an empty list
32+
should be returned.
33+
34+
Implement the MovieRentingSystem class:
35+
- MovieRentingSystem(int n, int[][] entries) Initializes the MovieRentingSystem
36+
object with n shops and the movies in entries.
37+
- List<Integer> search(int movie) Returns a list of shops that have an unrented copy
38+
of the given movie as described above.
39+
- void rent(int shop, int movie) Rents the given movie from the given shop.
40+
- void drop(int shop, int movie) Drops off a previously rented movie at the given
41+
shop.
42+
- List<List<Integer>> report() Returns a list of cheapest rented movies as describe
43+
above.
44+
45+
Note: The test cases will be generated such that rent will only be called if the
46+
shop has an unrented copy of the movie, and drop will only be called if the shop
47+
had previously rented out the movie.
48+
"""
49+
50+
def __init__(self, n: int, entries: List[List[int]]):
51+
# Dictionary
52+
# Key: (Shop, Movie)
53+
# Value: Price
54+
self.shop_movie_to_price = collections.defaultdict(dict)
55+
56+
# Dictionary
57+
# Key: Movie
58+
# Value: RentingItem
59+
self.unrented_movie_to_item = collections.defaultdict(list)
60+
61+
# RentingItem
62+
self.rented_item = []
63+
64+
# Sets for managing hashmaps as we cannot remove non-top items
65+
self.rented = set()
66+
self.returned = set()
67+
68+
for entry in entries:
69+
shop, movie, price = entry
70+
self.shop_movie_to_price[shop][movie] = price
71+
heapq.heappush(self.unrented_movie_to_item[movie], (price, shop, movie))
72+
73+
def search(self, movie: int) -> List[int]:
74+
# Get the 5 cheapest shops
75+
res = []
76+
items = []
77+
while self.unrented_movie_to_item[movie] and len(res) < 5:
78+
while (
79+
self.unrented_movie_to_item[movie]
80+
and self.unrented_movie_to_item[movie][0] in self.rented
81+
):
82+
item = heapq.heappop(self.unrented_movie_to_item[movie])
83+
self.rented.remove(item)
84+
if self.unrented_movie_to_item[movie]:
85+
item = heapq.heappop(self.unrented_movie_to_item[movie])
86+
res.append(item[1])
87+
items.append(item)
88+
89+
# Append the 5 cheapest shops
90+
for item in items:
91+
heapq.heappush(self.unrented_movie_to_item[movie], item)
92+
return res
93+
94+
def rent(self, shop: int, movie: int) -> None:
95+
price = self.shop_movie_to_price[shop][movie]
96+
item = (price, shop, movie)
97+
self.rented.add(item)
98+
if item in self.returned:
99+
self.returned.remove(item)
100+
else:
101+
# Push the new rented item to the list of rented items
102+
heapq.heappush(self.rented_item, item)
103+
104+
def drop(self, shop: int, movie: int) -> None:
105+
price = self.shop_movie_to_price[shop][movie]
106+
item = (price, shop, movie)
107+
self.returned.add(item)
108+
if item in self.rented:
109+
self.rented.remove(item)
110+
else:
111+
# Push the new not rented item to the list of non-rented items
112+
heapq.heappush(self.unrented_movie_to_item[movie], item)
113+
114+
def report(self) -> List[List[int]]:
115+
# Get the 5 cheapest rented movies
116+
res = []
117+
items = []
118+
while self.rented_item and len(res) < 5:
119+
while self.rented_item and self.rented_item[0] in self.returned:
120+
item = heapq.heappop(self.rented_item)
121+
self.returned.remove(item)
122+
if self.rented_item:
123+
item = heapq.heappop(self.rented_item)
124+
res.append([item[1], item[2]])
125+
items.append(item)
126+
127+
# Append the 5 cheapest movies
128+
for item in items:
129+
heapq.heappush(self.rented_item, item)
130+
return res
131+
132+
133+
# Your MovieRentingSystem object will be instantiated and called as such:
134+
# obj = MovieRentingSystem(n, entries)
135+
# param_1 = obj.search(movie)
136+
# obj.rent(shop,movie)
137+
# obj.drop(shop,movie)
138+
# param_4 = obj.report()
Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
from awesome_python_leetcode._1912_design_movie_rental_system import MovieRentingSystem
2+
3+
4+
def test_func():
5+
"""Tests the solution of a LeetCode problem."""
6+
system = MovieRentingSystem(
7+
3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]]
8+
)
9+
assert system.search(1) == [1, 0, 2]
10+
11+
system.rent(0, 1)
12+
system.rent(1, 2)
13+
assert system.report() == [[0, 1], [1, 2]]
14+
15+
system.drop(1, 2)
16+
assert system.search(2) == [0, 1]

0 commit comments

Comments
(0)

AltStyle によって変換されたページ (->オリジナル) /