636. Exclusive Time of Functions

Problem Description

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.

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.

The exclusive time of a function is the sum of execution times for all function calls in the program. Note that this does not include any time spent in nested calls.

Examples:

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.

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, executes for 4 units of time, and ends at the end of time 5.
Function 0 (initial call) resumes execution then immediately calls itself again at the beginning of time 6.
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 + 1 + 1 = 4 units of total time executing.

Constraints:

• 1 ≤ n ≤ 100
• 1 ≤ logs.length ≤ 500
• 0 ≤ function_id < n
• 0 ≤ timestamp ≤ 10⁹
• 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

Python Solution

class Solution:
    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:
        result = [0] * n
        stack = []  # (id, start_time)
        
        for log in logs:
            func_id, action, timestamp = log.split(':')
            func_id, timestamp = int(func_id), int(timestamp)
            
            if action == 'start':
                if stack:
                    # Add time to the previous function
                    prev_id, prev_start = stack[-1]
                    result[prev_id] += timestamp - prev_start
                stack.append([func_id, timestamp])
            else:
                # End of function
                _, start_time = stack.pop()
                # Add time to current function (inclusive of end timestamp)
                result[func_id] += timestamp - start_time + 1
                if stack:
                    # Update start time for previous function
                    stack[-1][1] = timestamp + 1
                    
        return result

class Log:
    def __init__(self, log: str):
        func_id, action, timestamp = log.split(':')
        self.id = int(func_id)
        self.is_start = action == 'start'
        self.timestamp = int(timestamp)

class Solution:
    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:
        result = [0] * n
        stack = []  # Stack of function IDs
        
        logs = [Log(log) for log in logs]
        
        for log in logs:
            if log.is_start:
                if stack:
                    result[stack[-1]] += log.timestamp - prev_time
                stack.append(log.id)
                prev_time = log.timestamp
            else:
                result[stack.pop()] += log.timestamp - prev_time + 1
                prev_time = log.timestamp + 1
                
        return result

class Solution {
    public int[] exclusiveTime(int n, List logs) {
        int[] result = new int[n];
        Stack stack = new Stack<>();  // [id, startTime]
        
        for (String log : logs) {
            String[] parts = log.split(":");
            int id = Integer.parseInt(parts[0]);
            String action = parts[1];
            int timestamp = Integer.parseInt(parts[2]);
            
            if (action.equals("start")) {
                if (!stack.isEmpty()) {
                    Integer[] prev = stack.peek();
                    result[prev[0]] += timestamp - prev[1];
                }
                stack.push(new Integer[]{id, timestamp});
            } else {
                Integer[] current = stack.pop();
                result[id] += timestamp - current[1] + 1;
                if (!stack.isEmpty()) {
                    stack.peek()[1] = timestamp + 1;
                }
            }
        }
        
        return result;
    }
}

class Solution {
    private record Log(int id, boolean isStart, int timestamp) {
        static Log parse(String log) {
            String[] parts = log.split(":");
            return new Log(
                Integer.parseInt(parts[0]),
                parts[1].equals("start"),
                Integer.parseInt(parts[2])
            );
        }
    }
    
    public int[] exclusiveTime(int n, List logs) {
        int[] result = new int[n];
        Stack stack = new Stack<>();
        int prevTime = 0;
        
        for (String logStr : logs) {
            Log log = Log.parse(logStr);
            
            if (log.isStart) {
                if (!stack.isEmpty()) {
                    result[stack.peek()] += log.timestamp - prevTime;
                }
                stack.push(log.id);
                prevTime = log.timestamp;
            } else {
                result[stack.pop()] += log.timestamp - prevTime + 1;
                prevTime = log.timestamp + 1;
            }
        }
        
        return result;
    }
}

class Solution {
public:
    vector exclusiveTime(int n, vector& logs) {
        vector result(n, 0);
        stack> st;  // {id, start_time}
        
        for (const string& log : logs) {
            stringstream ss(log);
            string idStr, action, timeStr;
            getline(ss, idStr, ':');
            getline(ss, action, ':');
            getline(ss, timeStr, ':');
            
            int id = stoi(idStr);
            int timestamp = stoi(timeStr);
            
            if (action == "start") {
                if (!st.empty()) {
                    auto [prev_id, prev_start] = st.top();
                    result[prev_id] += timestamp - prev_start;
                }
                st.push({id, timestamp});
            } else {
                auto [curr_id, start_time] = st.top();
                st.pop();
                result[id] += timestamp - start_time + 1;
                if (!st.empty()) {
                    st.top().second = timestamp + 1;
                }
            }
        }
        
        return result;
    }
};

class Solution {
    struct Log {
        int id;
        bool is_start;
        int timestamp;
        
        Log(const string& log) {
            stringstream ss(log);
            string id_str, action, time_str;
            getline(ss, id_str, ':');
            getline(ss, action, ':');
            getline(ss, time_str, ':');
            
            id = stoi(id_str);
            is_start = action == "start";
            timestamp = stoi(time_str);
        }
    };
    
public:
    vector exclusiveTime(int n, vector& logs) {
        vector result(n, 0);
        stack st;
        int prev_time = 0;
        
        for (const string& log_str : logs) {
            Log log(log_str);
            
            if (log.is_start) {
                if (!st.empty()) {
                    result[st.top()] += log.timestamp - prev_time;
                }
                st.push(log.id);
                prev_time = log.timestamp;
            } else {
                result[st.top()] += log.timestamp - prev_time + 1;
                st.pop();
                prev_time = log.timestamp + 1;
            }
        }
        
        return result;
    }
};

/**
 * @param {number} n
 * @param {string[]} logs
 * @return {number[]}
 */
var exclusiveTime = function(n, logs) {
    const result = new Array(n).fill(0);
    const stack = [];  // [id, startTime]
    
    for (const log of logs) {
        const [id, action, timestamp] = log.split(':');
        const funcId = parseInt(id);
        const time = parseInt(timestamp);
        
        if (action === 'start') {
            if (stack.length > 0) {
                const [prevId, prevStart] = stack[stack.length - 1];
                result[prevId] += time - prevStart;
            }
            stack.push([funcId, time]);
        } else {
            const [currId, startTime] = stack.pop();
            result[funcId] += time - startTime + 1;
            if (stack.length > 0) {
                stack[stack.length - 1][1] = time + 1;
            }
        }
    }
    
    return result;
};

class Log {
    constructor(log) {
        const [id, action, timestamp] = log.split(':');
        this.id = parseInt(id);
        this.isStart = action === 'start';
        this.timestamp = parseInt(timestamp);
    }
}

/**
 * @param {number} n
 * @param {string[]} logs
 * @return {number[]}
 */
var exclusiveTime = function(n, logs) {
    const result = new Array(n).fill(0);
    const stack = [];
    let prevTime = 0;
    
    logs = logs.map(log => new Log(log));
    
    for (const log of logs) {
        if (log.isStart) {
            if (stack.length > 0) {
                result[stack[stack.length - 1]] += log.timestamp - prevTime;
            }
            stack.push(log.id);
            prevTime = log.timestamp;
        } else {
            result[stack.pop()] += log.timestamp - prevTime + 1;
            prevTime = log.timestamp + 1;
        }
    }
    
    return result;
};

public class Solution {
    public int[] ExclusiveTime(int n, IList logs) {
        var result = new int[n];
        var stack = new Stack<(int id, int startTime)>();
        
        foreach (var log in logs) {
            var parts = log.Split(':');
            var id = int.Parse(parts[0]);
            var action = parts[1];
            var timestamp = int.Parse(parts[2]);
            
            if (action == "start") {
                if (stack.Count > 0) {
                    var (prevId, prevStart) = stack.Peek();
                    result[prevId] += timestamp - prevStart;
                }
                stack.Push((id, timestamp));
            } else {
                var (currId, startTime) = stack.Pop();
                result[id] += timestamp - startTime + 1;
                if (stack.Count > 0) {
                    var prev = stack.Pop();
                    stack.Push((prev.id, timestamp + 1));
                }
            }
        }
        
        return result;
    }
}

public class Solution {
    private record Log(int Id, bool IsStart, int Timestamp) {
        public static Log Parse(string log) {
            var parts = log.Split(':');
            return new Log(
                int.Parse(parts[0]),
                parts[1] == "start",
                int.Parse(parts[2])
            );
        }
    }
    
    public int[] ExclusiveTime(int n, IList logs) {
        var result = new int[n];
        var stack = new Stack();
        var prevTime = 0;
        
        var parsedLogs = logs.Select(Log.Parse);
        
        foreach (var log in parsedLogs) {
            if (log.IsStart) {
                if (stack.Count > 0) {
                    result[stack.Peek()] += log.Timestamp - prevTime;
                }
                stack.Push(log.Id);
                prevTime = log.Timestamp;
            } else {
                result[stack.Pop()] += log.Timestamp - prevTime + 1;
                prevTime = log.Timestamp + 1;
            }
        }
        
        return result;
    }
}