#636

Exclusive Time of Functions

specialist · 690 · lc medium +30 · verified · 66.2% accepted · 2,319 likes · top 71%

Description

A single-threaded CPU runs n functions (IDs 0 to n-1). You receive a list logs where each entry is "id:start|end:timestamp". Each start log means the function began executing at the given timestamp; each end log means it finished at the end of that timestamp. Functions may call each other or recurse. Compute the exclusive CPU time (total time not interrupted by nested calls) for every function and return it as an array indexed by function ID.

Example 1:

Input: n = 2, logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]

Output: [3,4]

Explanation:

Function 0 starts at the beginning of time 0, then it executes 2 for units of time and reaches the end of time 1.

Function 1 starts at the beginning of time 2, executes for 4 units of time, and ends at the end of time 5.

Function 0 resumes execution at the beginning of time 6 and executes for 1 unit of time.

So function 0 spends 2 + 1 = 3 units of total time executing, and function 1 spends 4 units of total time executing.

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]

Explanation:

Function 0 starts at the beginning of time 0, executes for 2 units of time, and recursively calls itself.

Function 0 (recursive call) starts at the beginning of time 2 and executes for 4 units of time.

Function 0 (initial call) resumes execution then immediately calls itself again.

Function 0 (2nd recursive call) starts at the beginning of time 6 and executes for 1 unit of time.

Function 0 (initial call) resumes execution at the beginning of time 7 and executes for 1 unit of time.

So function 0 spends 2 + 4 + 1 + 1 = 8 units of total time executing.

Example 3:

Input: n = 2, logs = ["0:start:0","0:start:2","0:end:5","1:start:6","1:end:6","0:end:7"]

Output: [7,1]

Explanation:

Function 0 starts at the beginning of time 0, executes for 2 units of time, and recursively calls itself.

Function 0 (recursive call) starts at the beginning of time 2 and executes for 4 units of time.

Function 0 (initial call) resumes execution then immediately calls function 1.

Function 1 starts at the beginning of time 6, executes 1 unit of time, and ends at the end of time 6.

Function 0 resumes execution at the beginning of time 6 and executes for 2 units of time.

So function 0 spends 2 + 4 + 1 = 7 units of total time executing, and function 1 spends 1 unit of total time executing.

Code

1

2

3

class Solution:
    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:

class Solution:
    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]: