Friday, May 24, 2019

LeetCode [636] Exclusive Time of Functions

On a single threaded CPU, we execute some functions.  Each function has a unique id between 0 and N-1.
We store logs in timestamp order that describe when a function is entered or exited.
Each log is a string with this format: "{function_id}:{"start" | "end"}:{timestamp}".  For example, "0:start:3" means the function with id 0 started at the beginning of timestamp 3.  "1:end:2" means the function with id 1 ended at the end of timestamp 2.
A function's exclusive time is the number of units of time spent in this function.  Note that this does not include any recursive calls to child functions.
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 the beginning of time 0, then it executes 2 units of time and reaches the end of time 1.
Now function 1 starts at the beginning of time 2, executes 4 units of time and ends at time 5.
Function 0 is running again at the beginning of time 6, and also ends at the end of time 6, thus executing 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.

Note:
  1. 1 <= n <= 100
  2. Two functions won't start or end at the same time.
  3. Functions will always log when they exit.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    vector<string> splitStr(string s)
    {
        vector<string> ret;
        stringstream ss(s);
        string tmp;
        while(getline(ss, tmp, ':')) ret.push_back(tmp);
        return ret;
    }
    
    vector<int> exclusiveTime(int n, vector<string>& logs) {
        vector<int> ret(n, 0);
        stack<vector<int>> stk;//id, start time
        
        for(auto l:logs)
        {
            vector<string> r = splitStr(l);
            if(r[1]=="start"){
                stk.push(vector<int>{stoi(r[0]), stoi(r[2])});
            }else{//end
                int id = stoi(r[0]);
                int len = stoi(r[2])-stk.top()[1]+1;
                ret[id] += len;

                stk.pop();
                if(!stk.empty()){
                    ret[stk.top()[0]] -= len;
                }
            }
        }
        return ret;
    }
};


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    class Log{
        int id;
        int timeStamp;
        String state;
        Log(int i, int t, String s){
            id = i;
            timeStamp = t;
            state = s;
        }
    }

    Log parse(String log){
        int i1 = log.indexOf(':');
        int i2 = log.indexOf(':', i1+1);
        int id = Integer.parseInt(log.substring(0, i1));
        int ts = Integer.parseInt(log.substring(i2+1));
        String state = log.substring(i1+1, i2);
        return new Log(id, ts, state);
    }

    public int[] exclusiveTime(int n, List<String> logs) {
        int[] res = new int[n];
        Stack<Log> stk = new Stack<>();
        for(String log : logs){
            Log newLog = parse(log);
            if(newLog.state.equals("start")){
                stk.push(newLog);
            }else{
                int dur = newLog.timeStamp - stk.pop().timeStamp + 1;
                res[newLog.id] += dur;
                if(!stk.isEmpty()){
                    res[stk.peek().id] -= dur;
                }
            }
        }
        return res;
    }
}
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)