Solve Rooms and Top-K Streams

Problem Statement

Design a data processing system, StreamRoomManager, that dynamically schedules video streaming jobs onto virtual compute rooms and tracks usage statistics across streams in real time.

Each streaming session has a start time, an end time, and a unique stream_id. Sessions arrive in non-decreasing order of start_time (start_time int: Schedules a session in the half-open interval [start, end). It must assign the session to the available room with the smallest room ID (0-indexed). A room is available at time start if its previously assigned session ended at or before start. If no existing room is free, open a new room with index equal to the total number of rooms currently created. Returns the room ID assigned.

• top_k_streams(k: int) -> list[str]: Returns the IDs of the top k streams ranked by total accumulated duration (end - start) across all sessions processed so far. Ties in total duration should be broken in lexicographical (alphabetical) order of stream_id. If fewer than k unique streams exist, return all of them in ranked order.

Class Interface

class StreamRoomManager:
    def __init__(self):
        pass

    def schedule(self, start: int, end: int, stream_id: str) -> int:
        pass

    def top_k_streams(self, k: int) -> list[str]:
        pass

Constraints

• 0 <= start < end <= 10^9
• start values across successive calls to schedule are monotonically non-decreasing: start_i <= start_{i+1}.
• Total number of calls to schedule and top_k_streams is at most 10^5.
• 1 <= len(stream_id) <= 32, consisting of lowercase English letters.
• 1 <= k <= 1000.

Example

manager = StreamRoomManager()

# Room 0 is created and assigned
manager.schedule(1, 5, "stream_a")  # returns 0 (duration: 4)

# Room 0 is busy until 5; Room 1 is created and assigned
manager.schedule(2, 6, "stream_b")  # returns 1 (duration: 4)

# Room 0 is freed at 5; assigned Room 0
manager.schedule(5, 8, "stream_c")  # returns 0 (duration: 3)

# Room 1 is freed at 6; assigned Room 1
manager.schedule(7, 10, "stream_a") # returns 1 (duration: 3 for stream_a, total: 7)

# stream_a has duration 7, stream_b has 4, stream_c has 3
manager.top_k_streams(2) # returns ["stream_a", "stream_b"]

Edge Cases

• Multiple rooms free at the exact same moment: pick the one with the smallest index.
• Session of length zero (though constraints specify start < end, handle equal duration ties gracefully).
• k exceeds the number of unique streams processed so far: return all streams sorted by ranking criteria.