636. Exclusive Time of Functions

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.

class Solution {
    struct log{
        int function;
        string status;
        int time;
    };
    vector<int> res;
    const char COLON = ':';
    const string START = "start";
    const string END = "end";
    log convert(string& str) {
        stringstream ss(str);
        string function, status, time;
        getline(ss, function, COLON);
        getline(ss, status, COLON);
        getline(ss, time, COLON);
        return {stoi(function), status, stoi(time)};
    }
    int calc(vector<string>& logs, int& i, int time) {
        int minus(0);
        log lg;
        for(; i < logs.size(); i++) {
            lg = convert(logs[i]);
            if(lg.status == START) {
                minus += calc(logs, ++i, lg.time);
            } else {
                res[lg.function] += lg.time - time + 1 - minus;
                return lg.time - time + 1;
            }
        }
        return lg.time - time + 1;
    }
public:
    vector<int> exclusiveTime(int n, vector<string>& logs) {
        res = vector<int>(n);
        int i, minus(0), t;
        log lg;
        for(i = 0; i < logs.size(); i++) {
            lg = convert(logs[i]);
            if(lg.status == START) {
                t = lg.time;
                minus += calc(logs, ++i, lg.time);
            } else {
                res[lg.function] += lg.time - t + 1 - minus; minus = 0;
            }
        }
        return res;
    }
};