Design Movie Rental System
Problem
Build a class for n shops. Each entry [shop, movie, price] places one copy of a movie at a shop. Support: search(movie) — the cheapest 5 shops with an unrented copy (tie → smaller shop first); rent(shop, movie); drop(shop, movie); and report() — the cheapest 5 rented copies as [shop, movie] (ties break by price, then shop, then movie).
n = 3, entries = [[0,1,5],[0,2,6],[0,3,7],[1,1,4],[1,2,7],[2,1,5]]search(1)=[1,0,2]; rent(0,1); rent(1,2); report()=[[0,1],[1,2]]; drop(1,2); search(2)=[0,1]from sortedcontainers import SortedList
class MovieRentingSystem:
def __init__(self, n, entries):
self.price = {} # (shop, movie) -> price
self.avail = {} # movie -> SortedList[(price, shop)]
self.rented = SortedList() # global (price, shop, movie)
for shop, movie, price in entries:
self.price[(shop, movie)] = price
self.avail.setdefault(movie, SortedList()).add((price, shop))
def search(self, movie):
# cheapest 5 unrented shops for this movie
lst = self.avail.get(movie, [])
return [shop for price, shop in lst[:5]]
def rent(self, shop, movie):
price = self.price[(shop, movie)]
self.avail[movie].remove((price, shop)) # leaves the available set
self.rented.add((price, shop, movie)) # enters the rented set
def drop(self, shop, movie):
price = self.price[(shop, movie)]
self.rented.remove((price, shop, movie)) # leaves the rented set
self.avail[movie].add((price, shop)) # back to available
def report(self):
# cheapest 5 rented copies as [shop, movie]
return [[shop, movie] for price, shop, movie in self.rented[:5]]class MovieRentingSystem {
constructor(n, entries) {
this.price = new Map(); // "shop,movie" -> price
this.avail = new Map(); // movie -> sorted [price, shop]
this.rented = []; // global sorted [price, shop, movie]
for (const [shop, movie, price] of entries) {
this.price.set(shop + "," + movie, price);
if (!this.avail.has(movie)) this.avail.set(movie, []);
insort(this.avail.get(movie), [price, shop]);
}
}
search(movie) {
const lst = this.avail.get(movie) || [];
return lst.slice(0, 5).map(([price, shop]) => shop); // cheapest 5 shops
}
rent(shop, movie) {
const price = this.price.get(shop + "," + movie);
erase(this.avail.get(movie), [price, shop]); // leaves available
insort(this.rented, [price, shop, movie]); // enters rented
}
drop(shop, movie) {
const price = this.price.get(shop + "," + movie);
erase(this.rented, [price, shop, movie]); // leaves rented
insort(this.avail.get(movie), [price, shop]); // back to available
}
report() {
return this.rented.slice(0, 5).map(([p, shop, movie]) => [shop, movie]);
}
}
// insort / erase keep an array sorted by tuple order (binary search + splice)class MovieRentingSystem {
Map<Long, Integer> price = new HashMap<>(); // shop*K+movie -> price
Map<Integer, TreeSet<int[]>> avail = new HashMap<>(); // movie -> {price, shop}
TreeSet<int[]> rented; // global {price, shop, movie}
final long K = 100000L;
public MovieRentingSystem(int n, int[][] entries) {
Comparator<int[]> cmp = (a, b) -> a[0] != b[0] ? a[0] - b[0]
: a[1] != b[1] ? a[1] - b[1] : a[2] - b[2];
rented = new TreeSet<>(cmp);
for (int[] e : entries) {
price.put(e[0] * K + e[1], e[2]);
avail.computeIfAbsent(e[1], k -> new TreeSet<>(cmp)).add(new int[]{e[2], e[0]});
}
}
public List<Integer> search(int movie) {
List<Integer> res = new ArrayList<>();
for (int[] p : avail.getOrDefault(movie, new TreeSet<>())) {
if (res.size() == 5) break;
res.add(p[1]); // cheapest 5 shops
}
return res;
}
public void rent(int shop, int movie) {
int p = price.get(shop * K + movie);
avail.get(movie).remove(new int[]{p, shop}); // leaves available
rented.add(new int[]{p, shop, movie}); // enters rented
}
public void drop(int shop, int movie) {
int p = price.get(shop * K + movie);
rented.remove(new int[]{p, shop, movie}); // leaves rented
avail.get(movie).add(new int[]{p, shop}); // back to available
}
public List<List<Integer>> report() {
List<List<Integer>> res = new ArrayList<>();
for (int[] r : rented) {
if (res.size() == 5) break;
res.add(Arrays.asList(r[1], r[2])); // [shop, movie]
}
return res;
}
}class MovieRentingSystem {
unordered_map<long long, int> price; // shop*K+movie -> price
unordered_map<int, set<pair<int,int>>> avail; // movie -> {price, shop}
set<array<int,3>> rented; // global {price, shop, movie}
const long long K = 100000LL;
public:
MovieRentingSystem(int n, vector<vector<int>>& entries) {
for (auto& e : entries) {
price[(long long)e[0] * K + e[1]] = e[2];
avail[e[1]].insert({e[2], e[0]});
}
}
vector<int> search(int movie) {
vector<int> res;
for (auto& p : avail[movie]) {
if (res.size() == 5) break;
res.push_back(p.second); // cheapest 5 shops
}
return res;
}
void rent(int shop, int movie) {
int p = price[(long long)shop * K + movie];
avail[movie].erase({p, shop}); // leaves available
rented.insert({p, shop, movie}); // enters rented
}
void drop(int shop, int movie) {
int p = price[(long long)shop * K + movie];
rented.erase({p, shop, movie}); // leaves rented
avail[movie].insert({p, shop}); // back to available
}
vector<vector<int>> report() {
vector<vector<int>> res;
for (auto& r : rented) {
if (res.size() == 5) break;
res.push_back({r[1], r[2]}); // [shop, movie]
}
return res;
}
};Explanation
The trick is to keep every "give me the cheapest" answer pre-sorted so search and report are just reads from the front of an ordered structure. We maintain three things: a price map from (shop, movie) to its rental price, a per-movie sorted set avail[movie] of (price, shop) for copies that are currently unrented, and one global sorted set rented of (price, shop, movie) for copies that are out.
Ordering tuples this way bakes the tie rules straight into the data structure. In avail[movie], comparing (price, shop) means cheaper first and ties break on the smaller shop — exactly what search needs. In rented, comparing (price, shop, movie) breaks ties by price, then shop, then movie — exactly what report needs. So search reads the first 5 entries of avail[movie], and report reads the first 5 of rented.
rent(shop, movie) looks up the price, removes (price, shop) from avail[movie], and inserts (price, shop, movie) into rented. drop(shop, movie) does the reverse: remove from rented, add back to avail[movie]. Each move is one delete and one insert into balanced trees, so it is O(log n).
Walking the example: movie 1 starts unrented at shops 1 (price 4), 0 (price 5) and 2 (price 5), so search(1) returns [1, 0, 2]. After rent(0, 1) and rent(1, 2), the rented set holds (5, 0, 1) and (7, 1, 2), so report() gives [[0, 1], [1, 2]]. Then drop(1, 2) returns movie 2 to shop 1, and search(2) returns [0, 1].