Problem Brief

Service Timeout Detection

FULLTIMENEW GRADOA

Heartbeat events are recorded with a timestamp and a service identifier. A service times out if the gap between any two consecutive heartbeats for that service is strictly greater than a given threshold.

Return all service identifiers that time out at least once, sorted lexicographically.

1Example 1

Input

timestamps = [10, 20, 80, 10, 65], serviceIds = ["svc1", "svc1", "svc1", "svc2", "svc2"], threshold = 30

Output

["svc1", "svc2"]

Explanation

svc1 has a 60-second gap between heartbeats at 20 and 80, and svc2 has a 55-second gap between 10 and 65. Both exceed the threshold.

Constraints

Limits and guarantees your solution can rely on.

1 <= n <= 2 * 10^5
1 <= timestamps[i] <= 10^9
0 <= threshold <= 10^9

Draft autosaves locally

public String[] detectTimedOutServices(int[] timestamps, String[] serviceIds, int threshold) {
  // write your code here
}

Input

timestamps

[10, 20, 80, 10, 65]

serviceIds

["svc1", "svc1", "svc1", "svc2", "svc2"]

threshold

Output

["svc1", "svc2"]