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 from 0 to n-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） 如果一function在time 0 start， 在time 0 end，那么它用了1 unit of time，而不是0， 这意味着当一个function end时，所花的是时间应该是end time + 1再减之前的时间， 这也是为什么接下来的解法里， 当我们知道一个function end时，res[stack.peek()]要加1

（2）这题假设输入都是valid, 这里的valid指的是如果function A call function B, 那么function B一定会在function A之前end

这题适合用stack来做，我们维护一个长为n的数组res, res里的index分别代表funtion的id, 而值则是每个function的执行时间。对于输入的每个log, 我们将它分为三部分：id, start/end指标，时间，如果此时栈不为空，则说明之前有函数在运行，所以那个函数的时间要增加，增加的量为当前函数的时间减去 之前得到的时间prevTime. 如果当前的log表示的是start, 则将当前函数的id压入栈，更新prevTime, 如果是end，则出栈。

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

        int[] res = new int[n];
        Stack<Integer> stack = new Stack<>();
        int prevTime = 0;
        int curTime = 0;
        String[] curLog;

        for (int i = 0; i < logs.size(); i++) {
            curLog = logs.get(i).split(":");
            curTime = Integer.parseInt(curLog[2]);

            if (!stack.isEmpty()) {
                res[stack.peek()] += curTime - prevTime;
            }

            if (curLog[1].equals("start")) {
               stack.push(Integer.parseInt(curLog[0]));
               prevTime = curTime;
            }
            else {
                ++res[stack.peek()];
                prevTime = curTime + 1;
                stack.pop();
            }
        }
        return res;
    }
}

3. Time & Space Complexity

时间和空间都是O(n)