Reason About a Movie Billboard Rotation Component

Movie Billboard Rotation Component

You are tasked with building a billboard rotation engine that selects the next movie title to display based on a combination of a 'priority score' and 'last displayed timestamp.'

Instead of a heap, you must maintain state using two ordered maps:

1. PriorityMap: Maps (priority_score, movie_id) to movie_metadata.
2. TimestampMap: Maps (last_displayed_timestamp, movie_id) to movie_metadata.

Requirements

Implement a class BillboardManager with the following interface:

class BillboardManager:
    def add_movie(self, movie_id, priority):
        # Adds a new movie with initial priority and timestamp 0
        pass

    def get_next_movie(self):
        # Returns the movie_id that should be displayed next.
        # Selection logic: prioritize highest priority, then oldest timestamp.
        pass

    def update_display(self, movie_id):
        # Updates the movie's last_displayed_timestamp to the current system time
        # and refreshes its position in the internal maps.
        pass

Constraints

• movie_id is a unique string.
• priority is a float.
• Ensure update_display operations maintain the invariants of both ordered maps.
• Time complexity for get_next_movie and update_display should ideally be O(log N).

Example

• Initial state: Movie A (p=10), Movie B (p=5).
• get_next_movie() returns A (highest priority).
• update_display('A') sets A's timestamp to T1.
• A subsequent get_next_movie() call must consider the updated timestamp for future tie-breaking if priorities are identical.