Merge intervals and design rating APIs

Agent Management System

Design an in-memory agent management system, AgentTracker, that tracks customer support agent work shifts and review ratings.

Your class should support the following operations:

1. add_shift(agent_id: str, start: int, end: int) -> None: Records a shift interval [start, end] during which the agent was active. Shifts may overlap or arrive out of order.
2. get_merged_shifts(agent_id: str) -> list[list[int]]: Returns a list of mutually disjoint, non-overlapping intervals [start_i, end_i] representing the agent's total logged shift coverage, sorted in ascending order of start time. Adjacent intervals that touch (e.g., [1, 3] and [3, 5]) should be merged into a single interval ([1, 5]).
3. record_rating(agent_id: str, score: int) -> None: Records an integer satisfaction rating (1 list[tuple[str, float]]**: Returns up to k agents sorted by their average rating in descending order. If two agents have the same average rating, break ties by agent_id in lexicographical (alphabetical) ascending order. Each element should be a tuple (agent_id, avg_score). Agents with no ratings should not be included.

Class Interface

class AgentTracker:
    def __init__(self):
        pass

    def add_shift(self, agent_id: str, start: int, end: int) -> None:
        pass

    def get_merged_shifts(self, agent_id: str) -> list[list[int]]:
        pass

    def record_rating(self, agent_id: str, score: int) -> None:
        pass

    def get_top_agents(self, k: int) -> list[tuple[str, float]]:
        pass

Example

tracker = AgentTracker()

# Record shifts
tracker.add_shift("alice", 9, 12)
tracker.add_shift("alice", 11, 14)
tracker.add_shift("alice", 16, 18)
print(tracker.get_merged_shifts("alice"))
# Output: [[9, 14], [16, 18]]

# Record ratings
tracker.record_rating("alice", 5)
tracker.record_rating("alice", 3)  # alice avg: 4.0
tracker.record_rating("bob", 4)    # bob avg: 4.0
tracker.record_rating("charlie", 5)# charlie avg: 5.0

print(tracker.get_top_agents(2))
# Output: [("charlie", 5.0), ("alice", 4.0)]
# Explanation: charlie is rank 1 (5.0). alice and bob both have 4.0, but "alice" = 1`.
- At most `20,000` total calls across all methods.

### Edge Cases

- `get_merged_shifts` for an `agent_id` with no shifts should return `[]`.
- If fewer than `k` agents have received ratings, return all rated agents.
- Zero rated agents should result in `get_top_agents` returning `[]`.