636 Exclusive Time of Functions

636. Exclusive Time of Functions

1. Question

Given the running logs of n functions that are executed in a nonpreemptive single threaded CPU, find the exclusive time of these functions.

Each function has a unique id, start from0ton-1. A function may be called recursively or by another function.

A log is a string has this format :function_id:start_or_end:timestamp. For example,"0:start:0"means function 0 starts from the very beginning of time 0."0:end:0"means function 0 ends to the very end of time 0.

Exclusive time of a function is defined as the time spent within this function, the time spent by calling other functions should not be considered as this function's exclusive time. You should return the exclusive time of each function sorted by their 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 time 0, then it executes 2 units of time and reaches the end of time 1. 
Now function 0 calls function 1, function 1 starts at time 2, executes 4 units of time and end at time 5.
Function 0 is running again at time 6, and also end at the time 6, thus executes 1 unit of time. 
So function 0 totally execute 2 + 1 = 3 units of time, and function 1 totally execute 4 units of time.

Note:

1. Input logs will be sorted by timestamp, NOT log id.

2. Your output should be sorted by function id, which means the 0th element of your output corresponds to the exclusive time of function 0.

3. Two functions won't start or end at the same time.

4. Functions could be called recursively, and will always end.

5. 1 <= n <= 100

2. Implementation

(1) Stack

解析: 这题题意是给n个function，通过输入的list of log判断每个function运行的总时间分别是多少。Log 是以<function id : start/end: timestamp>的形式。

• 我们应该将每个时间作为一个单位判断, 即把每个时间想象成一个bucket

• 当log中的function是start时，表示log的时间点是下一个区间的起点，那么对于当前正在运行的function(stack顶存的function id)，其运行时间应该是当前log的时间curTime减去上次记录的时间preTime。因为curTime是下一个区间的起点，所以不应该加入当前的计算

• 当log中的function是end时，表示log的时间点是当前区间的终点，所以当前运行的function的所花的时间应该是curTime - preTime + 1，因为curTime此时被算作当前的区间，应该加入当期的计算，同时preTime更新为curTime + 1，表示下一个区间的起点

class Solution {
    public int[] exclusiveTime(int n, List<String> logs) {
        if (n <= 0 || logs == null || logs.size() == 0) {
            return new int[0];
        }

        Stack<Integer> stack = new Stack();
        // preTime is the start of interval
        int preTime = 0;
        int curTime = 0;

        int[] res = new int[n];

        for (String log : logs) {
            String[] parts = log.split(":");
            int id = Integer.parseInt(parts[0]);
            curTime = Integer.parseInt(parts[2]);

            if (parts[1].equals("start")) {
                if (!stack.isEmpty()) {
                    // curTime is the start of next interval, it doesn't belong to 
                    // current interval, should not count it here
                    res[stack.peek()] += curTime - preTime;
                }
                stack.push(id);
                preTime = curTime;
            }
            else {
                // curTime is the end of current interval, we should count it 
                // by plus 1 here
                res[stack.pop()] += curTime - preTime + 1;
                // Update preTime to start of next interval by plus 1
                preTime = curTime + 1;
            }
        }
        return res;
    }
}

3. Time & Space Complexity

Stack: 时间复杂度O(n), 空间复杂度O(n)