c++ stack solution with explanation


  • 0
    J

    Time used for inner loop thread need to be deducted from outer loop thread. If the log is start the thread, push it into stack. otherwise, calculate usedTime for current thread and deduct the time from parent thread. O(n) time

    class Solution {
    public:
        vector<int> exclusiveTime(int n, vector<string>& logs) {
            vector<int> ans(n, 0);
            stack<pair<int, int>> stk;
            size_t len = logs.size();
            int occupied = 0;
            for(int i=0; i<len; i++)
            {
                pair<int, int> logMeta;
                bool isStart = parseLog(logs[i], logMeta);
                if(isStart)
                {
                    stk.push(logMeta);
                }
                else
                {
                    pair<int, int> logStart = stk.top();
                    stk.pop();
                    int timeUsed = logMeta.second-logStart.second+1;
                    ans[logMeta.first] += timeUsed;
                    if(!stk.empty())
                        ans[stk.top().first] -= timeUsed;
                }
            }
            return ans;
        }
        
        bool parseLog(string& log, pair<int, int>& logMeta)
        {
            size_t pos=log.find(":");
            int threadId = stoi(log.substr(0, pos));
            size_t endPos = log.find(":", pos+1);
            bool isStart = ((log.substr(pos+1, 5)) == "start")?true:false;
            int timestamp = stoi(log.substr(endPos+1));
            logMeta = make_pair(threadId, timestamp);
            return isStart;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.