Problem Statement in English

You’re given an integer n, which indicates the number of movie shops in a city. Each shop has a collection of movies. You are also given a 2D integer array entries, where each entries[i] = [shop[i], movie[i], price[i]] indicates that the shop with ID shop[i] has the movie with ID movie[i] at a rental price of price[i].

Your task is to implement a movie rental system that supports the following operations:

  1. Search: Find 5 shops with the lowest rental price for a specific movie.
  2. Rent: Rent a movie from a shop.
  3. Drop: Drop a rented movie back to the shop.
  4. Report: Get a list of the 5 cheapest rented movies.

Tie breaker is the shop ID.

Approach

We can use a combination of data structures to efficiently implement the required operations. The main components are:

  1. Price Map: A dictionary to store the rental prices for each movie in each shop.
  2. Unrented Movies: A mapping from movie IDs to a sorted set of (price, shop) tuples, representing the shops that have the movie available for rent.
  3. Rented Movies: A sorted set of (price, shop, movie) tuples, representing the currently rented movies.

The operations can be implemented as follows:

  • Search: Retrieve 5 shops with the lowest rental price for the specified movie from the unrented mapping.
  • Rent: Move the movie from the unrented set to the rented set.
  • Drop: Move the movie back from the rented set to the unrented set.
  • Report: Retrieve the 5 cheapest rented movies from the rented set.

Solution in Python


class MovieRentingSystem:

    def __init__(self, n: int, entries: List[List[int]]):
        self.prices = {}
        self.unrented = defaultdict(SortedSet)
        self.rented = SortedSet()

        for shop, movie, p in entries:
            self.prices[(shop, movie)] = p
            self.unrented[movie].add((p, shop))

    def search(self, movie: int) -> List[int]:
        l = self.unrented[movie]
        res = []

        for p, shop in l[:5]:
            res.append(shop)
        return res

    def rent(self, shop: int, movie: int) -> None:
        p = self.prices[(shop, movie)]
        self.unrented[movie].remove((p, shop))
        self.rented.add((p, shop, movie))

    def drop(self, shop: int, movie: int) -> None:
        p = self.prices[(shop, movie)]
        self.rented.remove((p, shop, movie))
        self.unrented[movie].add((p, shop))
        
    def report(self) -> List[List[int]]:
        l = self.rented
        res = []

        for _, shop, movie in l[:5]:
            res.append((shop, movie))
        return res

Complexity

  • Time: $O(\log N)$ for each operation (search, rent, drop, report), where $N$ is the number of movies in the system.

  • Space: $O(N)$ for storing the movie rental information.

Mistakes I Made

I initially used a set instead of a SortedSet, which led to a TLE.

And we are done.