Compute the exclusive running time of each function from a sequence of start/end logs, excluding time spent in child calls.
Exclusive Time of Functions
You are given n functions labeled from 0 to n - 1 and a list of execution logs from a single-threaded program.
Each log entry has the form id:start:time or id:end:time:
idis the function idstartmeans the function began executing at the given timestampendmeans the function finished executing at the given timestamp
A function's exclusive time is the total time it spends running on the CPU excluding time consumed by any function it calls recursively or indirectly.
The logs are ordered chronologically and describe a valid execution trace. Because the CPU is single-threaded, at most one function is actively running at any moment.
Return an array where the i-th value is the exclusive time of function i.
Notes
- Timestamps are integer units.
- An
endtimestamp is inclusive: if a function ends at timet, it runs through that time unit. - A function may call itself recursively or call another function before finishing.
- The logs always form a valid sequence of nested calls and returns.
Input Format
Input Format
n: integer, number of functionslogs: array of strings, each string is in one of these formats:"id:start:time""id:end:time"
Output Format
Output Format
- Return an integer array of length
nwhere each position contains the exclusive time for that function id.
Constraints
Constraints
1 <= n <= 1001 <= logs.length <= 500- Each log entry is valid and appears in chronological order
- Function ids are between
0andn - 1 - Timestamps are non-negative integers
- The log sequence represents a valid nested execution trace
Example 1
Input
n = 2 logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]
Output
[3,4]
Explanation
Function 0 runs during time units 0-1 and 6, for a total of 3. Function 1 runs during time units 2-5, for a total of 4.
Example 2
Input
n = 1 logs = ["0:start:0","0:end:0"]
Output
[1]
Explanation
The single function runs for exactly one time unit, and the end timestamp is inclusive.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.