You are given a list of logs for jobs, requests, or RPC calls.
Each log entry contains:
- a job id
- a timestamp
- an event type:
START or END
You are also given an integer
timeoutThreshold.
A job starts when its
START log appears and finishes when its matching
END log appears.
A job is considered timed out if either:
- its
END log appears and endTimestamp - startTimestamp > timeoutThreshold, or
- at a current scan timestamp
t, if t - startTimestamp > timeoutThreshold even though its END log has not appeared yet.
Process the logs in chronological order and detect the earliest timeout that becomes known while scanning the logs.
Return the id of the first job that is detected to have timed out.
If multiple jobs become known to have timed out at the same timestamp, return the one with the smaller id.
If no job times out, return
-1.
Method Signature
int firstTimedOutJobId(List<String> logs, int timeoutThreshold)
logs[i] is in the format "jobId,timestamp,eventType"jobId is an integer id of the jobtimestamp is the time of that log entryeventType is either START or END- Return the first timed-out job id while scanning the logs
- Return
-1 if no job times out
Approach Clarification
While scanning the logs from left to right, a timeout may become known in two ways.
First, when an END log is seen, the matching job times out if its total duration is strictly greater than timeoutThreshold.
Second, before seeing an END log, a previously started job may already be known to have timed out if the current log timestamp is far enough ahead of that job's start timestamp.
Among all jobs that become known to have timed out at the same timestamp, return the smaller job id.
Constraints
1 ≤ logs.size() ≤ 200,0001 ≤ timeoutThreshold ≤ 10^91 ≤ jobId ≤ 10^9 for every parsed log entry0 ≤ timestamp ≤ 10^9 for every parsed log entry- Timestamps in
logs are in nondecreasing order
- Each log string contains exactly three comma-separated parts
eventType is either START or END
Examples
Example 1
Input
logs = List.of("1,1,START", "2,2,START", "1,4,END", "3,8,START", "3,15,END")
timeoutThreshold = 5
Method Call
firstTimedOutJobId(logs = List.of("1,1,START", "2,2,START", "1,4,END", "3,8,START", "3,15,END"), timeoutThreshold = 5)
Output
2
Explanation
Job 1 runs from timestamp 1 to 4, so duration = 3, which is not greater than 5.
When the scan reaches timestamp 8, job 2 has been active since timestamp 2, so 8 - 2 = 6 > 5. Therefore job 2 is now known to have timed out.
Job 3 also times out later, but the first detected timeout is job 2.
Example 2
Input
logs = List.of("5,1,START", "6,1,START", "5,7,END", "6,7,END")
timeoutThreshold = 5
Method Call
firstTimedOutJobId(logs = List.of("5,1,START", "6,1,START", "5,7,END", "6,7,END"), timeoutThreshold = 5)
Output
5
Explanation
Both jobs start at timestamp 1. At timestamp 7, both are known to have timed out because their durations are 6, which is greater than 5.
Since both timeouts become known at the same timestamp, return the smaller job id, which is 5.
Example 3
Input
logs = List.of("10,2,START", "10,7,END", "20,8,START", "20,13,END")
timeoutThreshold = 5
Method Call
firstTimedOutJobId(logs = List.of("10,2,START", "10,7,END", "20,8,START", "20,13,END"), timeoutThreshold = 5)
Output
-1
Explanation
Job 10 runs for 7 - 2 = 5 and job 20 runs for 13 - 8 = 5.
Since the timeout condition is strictly greater than timeoutThreshold, neither job times out.
Example 4
Input
logs = List.of("1,1,START", "2,3,START", "3,7,START")
timeoutThreshold = 4
Method Call
firstTimedOutJobId(logs = List.of("1,1,START", "2,3,START", "3,7,START"), timeoutThreshold = 4)
Output
1
Explanation
When the scan reaches timestamp 7, job 1 has been active since timestamp 1, so 7 - 1 = 6 > 4.
Job 2 has been active for 7 - 3 = 4, which is not greater than 4, so it is not timed out yet.
Therefore the first detected timeout is job 1.