636. Exclusive Time of Functions

Problem Statement

link: LeetCode.cn LeetCode 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:

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

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

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]

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.

Solution Approach

The solution uses a stack to track active function calls and calculates the exclusive time for each function by updating their durations based on the start and end log entries, adjusting for nested calls.

Algorithm

1. Stack Management: Use a stack to keep track of the active function calls, storing each function’s ID and its start time as you encounter “start” logs.
2. Time Calculation: When a “start” log is encountered, update the exclusive time of the function on top of the stack by adding the difference between the current and previous timestamps, then push the new function onto the stack.
3. End Log Handling: When an “end” log is encountered, pop the function from the stack, update its exclusive time by including the time from its start to its end, and adjust the start time of the function now on top of the stack for the next interval.

Implement

    class Solution:
    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:
        #"{function_id}:{"start" | "end"}:{timestamp}"
        #id   status   time
        # new task comes. res[-1]id += time - stack[-1]time  
        # end task comes res[id] += time - stack[-1]time & update end if not end else res[id] += time - end
        res = [0] * n
        st = []
        for log in logs:
            idx, tp, timestamp = log.split(':')
            idx, timestamp = int(idx), int(timestamp)
            if tp[0] == 's':
                if st:
                    res[st[-1][0]] += timestamp - st[-1][1]
                    st[-1][1] = timestamp
                st.append([idx, timestamp])
            else:
                i, t = st.pop()
                res[i] += timestamp - t + 1
                if st:
                    st[-1][1] = timestamp + 1
        return res

    
    

Twitter  facebook  Email