419. Function Time Ledger
A single-threaded program writes a log line each time one of its count functions starts or finishes. A line looks like "3:start:12" or "3:end:20": function id, the word start or end, and a timestamp. A start happens at the very beginning of that time unit and an end at the very end of it, so a function that starts and ends at time 5 ran for exactly one unit.
Functions may call other functions, even themselves, so while a callee runs the caller is paused. Return an array of length count whose entry i is the total time spent running function i itself, not counting the time of the functions it called. Lines are in time order and the log is always well formed.
Example 1
- Input:
- count = 3logs = ["1:start:2","0:start:4","0:end:5","2:start:6","2:end:9","1:end:11"]
- Output:
- [2,4,4]
- Explanation:
Function 1 runs for 2..3 (2 units) before calling 0, which runs 4..5. After 2 runs 6..9, function 1 resumes during 10..11. So function 1 gets 2 + 2 = 4 units, function 0 gets 2, function 2 gets 4.
Example 2
- Input:
- count = 2logs = ["0:start:0","0:start:1","0:end:3","0:end:4"]
- Output:
- [5,0]
- Explanation:
Function 0 calls itself. The inner call runs 1..3 (3 units); the outer one ran during 0 and 4, adding 2 units, so function 0 totals 5 and function 1 gets nothing.
Constraints
1 ≤ count ≤ 100
1 ≤ logs.length ≤ 20000, and logs.length is even
0 ≤ timestamp ≤ 109; timestamps never decrease through the log and the log describes a proper nesting of calls.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 400 msC++ 100 msJava 200 msJavaScript 200 msTypeScript 200 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)