In a Databricks Agent Framework deployment, tool calls from multiple agents are logged as a time-ordered stream. Implement an algorithm that returns the first timestamp when any agent exceeds a sliding-window limit, using standard data structures efficiently.
Given a list of events events, where each event is [timestamp, agent_id], and integers window_size and max_calls, return the earliest timestamp at which some agent_id has made more than max_calls calls within the inclusive window [timestamp - window_size + 1, timestamp]. If no agent violates the limit, return -1.
events: List[List[int, str]], window_size: int, max_calls: intintEvents are already sorted by non-decreasing timestamp. This models practical throttling for Databricks Foundation Model APIs or Model Serving requests issued by agents.
Example 1
events = [[1,"agentA"],[2,"agentA"],[3,"agentB"],[4,"agentA"]], window_size = 3, max_calls = 24agentA, the window at timestamp 4 is [2,4], containing calls at 2 and 4 plus the earlier call at 1 is excluded. Actually calls in [2,4] are 2 and 4, so no violation there; including timestamp 3 for agentB does not matter. The first violation would not occur, so this example is not violating. Use the second example for a violating case.Example 2
events = [[1,"agentA"],[2,"agentA"],[3,"agentA"]], window_size = 3, max_calls = 23agentA has 3 calls in window [1,3], exceeding the limit of 2.1 <= len(events) <= 10^51 <= window_size <= 10^91 <= max_calls <= 10^50 <= timestamp <= 10^9events is sorted by non-decreasing timestampagent_id is a non-empty string