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 <= 1001 <= logs.length <= 5000 <= function_id < n0 <= 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;
}
Input
Output
#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;
}
};
Input
Output
#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]);
}
}
}
Input
Output
#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
}
Input
Output
#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
Input
Output
#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;
}
}
}
Input
Output