Exclusive Time of Functions
Medium · stack
A program runs on a single thread and calls functions numbered 0 to n - 1. A function may call other functions, including itself. While a call is in progress, the function that made it waits.
You are given the log lines the program wrote, in order. Each line is one of:
"id:start:time": a call to functionidbegins at the very start of time unittime."id:end:time": a call to functionidfinishes at the very end of time unittime.
So a call logged as starting at 3 and ending at 5 lasts three units: 3, 4 and 5.
The exclusive time of a function is the number of time units in which it was the function actually running (the most recently started call that has not ended), added up over all of its calls. Time units in which no call is running count for nobody.
Return a list of length n whose entry i is the exclusive time of function i, which is 0 for a function that is never called.
The logs are always valid: every start has a matching end, calls nest properly, timestamps never decrease, and after an end log at time t the next log has a timestamp of at least t + 1.
Examples
Example 1
Input: n = 2, logs = ["0:start:0", "1:start:2", "1:end:5", "0:end:6"]
Output: [3, 4]
Function 0 runs during units 0 and 1, waits while function 1 runs during units 2 to 5, then runs again in unit 6: 3 units. Function 1 runs 4 units.
Example 2
Input: n = 1, logs = ["0:start:0", "0:start:2", "0:end:5", "0:start:6", "0:end:6", "0:end:7"]
Output: [8]
The function calls itself twice. Its own calls take 2 + 4 + 1 + 1 units.
Example 3
Input: n = 2, logs = ["0:start:1", "0:end:2", "1:start:5", "1:end:5"]
Output: [2, 1]
Units 3 and 4 have nothing running, so they count for nobody.
Constraints
- 1 <= n <= 100
- 2 <= len(logs) <= 3000
- Each log is "id:start:time" or "id:end:time" with 0 <= id < n and 0 <= time <= 10^9
- The logs are valid, as described above