Practice/Amazon/Leetcode 1912. Design Movie Rental System

Leetcode 1912. Design Movie Rental System

CodingOptional

Problem

Design a system to manage a movie rental business with multiple stores. The system needs to efficiently track which movies are available at which stores, handle rental and return operations, and provide quick lookups for:

1. Finding the cheapest stores that have a specific movie available (not currently rented)
2. Retrieving the list of currently rented movies ordered by rental price

Your system will be initialized with a set of stores and their movie inventory, where each entry specifies a store ID, movie ID, and the rental price at that store. The system must support the following operations:

• search(movie): Return up to 5 stores that have the specified movie available (unrented), ordered by price ascending. If prices are equal, order by store ID ascending. Return results as [shop, price] pairs.
• rent(shop, movie): Mark the movie at the specified shop as rented (removing it from available inventory).
• drop(shop, movie): Mark the movie at the specified shop as returned (adding it back to available inventory).
• report(): Return up to 5 currently rented movies ordered by price ascending. If prices are equal, order by shop ID ascending, then by movie ID ascending. Return results as [shop, movie, price] triples.

Requirements

1. Implement a MovieRentalSystem class that initializes with the number of stores n and a list of entries where each entry is [shop, movie, price]
2. The search operation must return results in O(log n) time per result retrieved
3. The rent and drop operations must efficiently update both the available and rented collections
4. The report operation must return results in O(1) time per result after maintaining a sorted collection
5. All query operations (search and report) return at most 5 results
6. Handle tie-breaking correctly according to the specified ordering rules

Constraints

• 1 ≤ n ≤ 3 × 105 (number of shops)
• 1 ≤ entries.length ≤ 105
• 1 ≤ shop ≤ n
• 1 ≤ movie, price ≤ 104
• Each shop carries at most one copy of any movie
• At most 3 × 104 calls total will be made to rent, drop, search, and report
• All rent operations refer to movies that are currently unrented
• All drop operations refer to movies that are currently rented

Examples

Example 1:

` Input: ["MovieRentalSystem", "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], [], [0, 1], [2]]

Output: [null, [[1, 4], [0, 5], [2, 5]], null, null, [[0, 1, 5], [1, 2, 7]], null, [[0, 6], [1, 7]]]

Explanation:

• Initialize system with 3 shops and their inventory
• search(1): Movie 1 is available at shop 1 for $4, shop 0 for $5, shop 2 for $5
• rent(0, 1): Rent movie 1 from shop 0
• rent(1, 2): Rent movie 2 from shop 1
• report(): Currently rented are [shop 0, movie 1, $5] and [shop 1, movie 2, $7]
• drop(0, 1): Return movie 1 to shop 0
• search(2): Movie 2 is now available at shop 0 for $6 and shop 1 for $7 `

Example 2:

` Input: ["MovieRentalSystem", "search", "search", "rent", "report"] [[2, [[0, 1, 10], [1, 1, 10]]], [1], [1], [0, 1], []]

Output: [null, [[0, 10], [1, 10]], [[0, 10], [1, 10]], null, [[0, 1, 10]]]

Explanation:

• When multiple stores have the same price, they are ordered by store ID
• After renting from store 0, only that rental appears in the report `