Algorithm

Problem Name: 636. Exclusive Time of Functions

On a single-threaded CPU, we execute a program containing `n` functions. Each function has a unique ID between `0` and `n-1`.

Function calls are stored in a call stack: when a function call starts, its ID is pushed onto the stack, and when a function call ends, its ID is popped off the stack. The function whose ID is at the top of the stack is the current function being executed. Each time a function starts or ends, we write a log with the ID, whether it started or ended, and the timestamp.

You are given a list `logs`, where `logs[i]` represents the `ith` log message formatted as a string `"{function_id}:{"start" | "end"}:{timestamp}"`. For example, `"0:start:3"` means a function call with function ID `0` started at the beginning of timestamp `3`, and `"1:end:2"` means a function call with function ID `1` ended at the end of timestamp `2`. Note that a function can be called multiple times, possibly recursively.

A function's exclusive time is the sum of execution times for all function calls in the program. For example, if a function is called twice, one call executing for `2` time units and another call executing for `1` time unit, the exclusive time is `2 + 1 = 3`.

Return the exclusive time of each function in an array, where the value at the `ith` index represents the exclusive time for the function with ID `i`.

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.
```

Constraints:

• `1 <= n <= 100`
• `1 <= logs.length <= 500`
• `0 <= function_id < n`
• `0 <= timestamp <= 109`
• No two start events will happen at the same timestamp.
• No two end events will happen at the same timestamp.
• Each function has an `"end"` log for each `"start"` log.

Code Examples

#1 Code Example with C Programming

```Code - C Programming```

``````
typedef struct {
int *p;
int *o; // offset
int sp;
int sz;
} s_t;

void push(s_t *stack, int tx) {
if (stack->sz == stack->sp) {
stack->sz *= 2;
stack->p = realloc(stack->p, stack->sz * sizeof(int));
//assert(stack->p);
stack->o = realloc(stack->o, stack->sz * sizeof(int));
//assert(stack->o);
}
stack->o[stack->sp   ] = 0;
stack->p[stack->sp ++] = tx;
}

int pop(s_t *stack) {
-- stack->sp;
if (stack->sp > 0) {
stack->o[stack->sp - 1] += stack->o[stack->sp];
}
return stack->p[stack->sp] + stack->o[stack->sp];
}

void update(s_t *stack, int tx) {
if (stack->sp > 0) {
stack->o[stack->sp - 1] += tx;
}
}

void parse(char *log, int *fid, int *d, int *t) {
char c;
*fid = 0;
while ((c = *(log ++)) != ':') {
*fid = (*fid) * 10 + c - '0';
}
if (*log == 'e') {  // end
log += 4;
*d = 0;
} else {
log += 6;
*d = 1;
}
*t = 0;
while ((c = *(log ++)) != 0) {
*t = (*t) * 10 + c - '0';
}
}

int* exclusiveTime(int n, char** logs, int logsSize, int* returnSize) {
s_t stack;
int *res, i, fid, d, t;

stack.sz = 100;
stack.sp = 0;
stack.p = malloc(stack.sz * sizeof(int));
//assert(stack.p);
stack.o = malloc(stack.sz * sizeof(int));
//assert(stack.o);

res = calloc(n, sizeof(int));
//assert(t);

*returnSize = n;

for (i = 0; i  <  logsSize; i ++) {
parse(logs[i], &fid, &d, &t);
if (d) {
push(&stack, t);
} else {
t = t - pop(&stack) + 1;
update(&stack, t);
res[fid] += t;
}
}

free(stack.p);
free(stack.o);

return res;
}
``````
Copy The Code &

Input

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

Output

cmd
[3,4]

#2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
private:
struct Log{
int id;
int time;
int append;
Log(int x, int y, int z): id(x), time(y), append(z){}
};

public:
vector<int> exclusiveTime(int n, vector < string>& logs) {
vector<int>res(n);
stack < Log*>s;
int id = 0, time = 0;
string op = "", str = "";
for(int i = 0; i  <  logs.size(); i++){
stringstream ss(logs[i]);
getline(ss, str, ':');
id = stoi(str);
getline(ss, str, ':');
op = str;
getline(ss, str, ':');
time = stoi(str);
Log* l = new Log(id, time, 0);
if(op == "start"){
if(!s.empty()) s.top()->append += l->time - s.top()->time;
s.push(l);
}
else{
res[id] += l->time - s.top()->time + 1 + s.top()->append;
s.pop();
if(!s.empty()) s.top()->time = l->time + 1;
}
}
return res;
}
};
``````
Copy The Code &

Input

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

Output

cmd
[3,4]

#3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int[] exclusiveTime(int n, List logs) {
int[] result = new int[n];
Stack < Log> stack = new Stack<>();
for (String log : logs) {
Log currentLog = new Log(log);
if (currentLog.isStart) {
stack.push(currentLog);
} else {
Log topLog = stack.pop();
result[topLog.id] += currentLog.time - topLog.time + 1 - topLog.overLappingTime;
if (!stack.isEmpty()) {
stack.peek().overLappingTime += currentLog.time - topLog.time + 1;
}
}
}
return result;
}

private static class Log {
public int id;
public boolean isStart;
public int time;
public int overLappingTime;

public Log(String log) {
String[] split = log.split(":");
this.id = Integer.parseInt(split[0]);
this.isStart = split[1].equals("start");
this.time = Integer.parseInt(split[2]);
}
}
}
``````
Copy The Code &

Input

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

Output

cmd
[8]

#4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const exclusiveTime = function (n, logs) {
const res = [...Array(n)].fill(0)
const stack = []
let pre = 0
for (let i = 0; i  <  logs.length; i++) {
const log = logs[i].split(':')
if (log[1] === 'start') {
if(stack.length !== 0) res[stack[stack.length - 1]] += +log[2] - pre
stack.push(log[0])
pre = log[2]
} else {
res[stack.pop()] += +log[2] - pre + 1
pre = +log[2] + 1
}
}
return res
}
``````
Copy The Code &

Input

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

Output

cmd
[8]

#5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def exclusiveTime(self, n, logs):
res, stack = [0] * n, []
for log in logs:
log = log.split(":")
if log[1] == "start":
stack.append([int(log[2]), 0])
else:
start = stack.pop()
time = int(log[2]) - start[0] + 1
res[int(log[0])] += time - start[1]
if stack:
stack[-1][1] += time
return res
``````
Copy The Code &

Input

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

Output

cmd
[7,1]

#6 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;

namespace LeetCode
{
public class _0636_ExclusiveTimeOfFunctions
{
public int[] ExclusiveTime(int n, IList < string> logs)
{
var stack = new Stack<int>();
var result = new int[n];

var start = 0;
foreach (var log in logs)
{
var str = log.Split(':');
var id = int.Parse(str[0]);
var time = int.Parse(str[2]);
if (str[1] == "start")
{
if (stack.Count > 0)
result[stack.Peek()] += time - start;
stack.Push(id);
start = time;
}
else
{
result[stack.Peek()] += time - start + 1;
stack.Pop();
start = time + 1;
}
}

return result;
}
}
}
``````
Copy The Code &

Input

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

Output

cmd
[7,1]
Advertisements