435. Exclusive Time of Functions
A single-threaded CPU runs n functions labeled 0 through n − 1. Functions may call one another, including themselves recursively; when a call happens, the caller pauses until the callee returns.
You receive the CPU's log as a list of strings, in chronological order. Each entry is either "{id}:start:{t}" — function id began executing at the beginning of time unit t — or "{id}:end:{t}" — function id returned at the end of time unit t. So a call logged as start:0 and end:0 ran for exactly 1 unit. The log is well-formed: every start has a matching end and calls nest properly.
The exclusive time of a function is the number of time units it spent executing itself, excluding any units spent inside functions it called. Your function receives n and logs and returns a list of n integers where entry i is function i's exclusive time summed across all of its invocations.
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 units 0–1 (2 units), gets interrupted by function 1 which runs units 2–5 (4 units), then function 0 resumes for unit 6 (1 more unit). Exclusive times: 0 → 3, 1 → 4.
Example 2:
Input: n = 1, logs = ["0:start:0", "0:start:2", "0:end:5", "0:end:6"]
Output: [7]
Explanation: Function 0 calls itself. The outer invocation runs units 0–1 and 6 (3 units), the recursive one runs units 2–5 (4 units) — all 7 units belong to function 0.
Constraints:
- 1 ≤ n ≤ 100
- 2 ≤ m ≤ 500 (m is even)
- 0 ≤ t ≤ 10⁹
- No two start entries share a timestamp, and no two end entries share a timestamp.
- The log is chronological and well-formed: starts and ends match and nest properly.
Hints:
The log is a stream of push (start) and pop (end) events for a call stack — at any instant, the function actually executing is the one on top. So the whole timeline is carved into segments between consecutive events, and each segment's units belong entirely to whoever was on top of the stack during it.
Keep a stack of function ids and a variable prev = the start of the not-yet-attributed time. On start at time t: credit t − prev units to the stack top (if any), push, set prev = t. On end at time t: credit t − prev + 1 units to the popped function (ends are inclusive!), set prev = t + 1.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 2, logs = ["0:start:0", "1:start:2", "1:end:5", "0:end:6"]
Expected output: [3, 4]