Thời gian độc quyền của hàm (Exclusive Time) trong C++

Mô tả bài toán

Cho log thực thi hàm đơn luồng: "id:start|end:timestamp". Tính thời gian độc quyền (thời gian thực thi trừ thời gian gọi hàm con) của mỗi hàm.

Ví dụ: n=2, logs=["0:start:0","1:start:2","1:end:5","0:end:6"] → [3,4] (hàm 0: 2+1=3, hàm 1: 4).

Giải thuật Stack

1. Duyệt log theo thứ tự.
2. Stack lưu ID hàm đang chạy.
3. Biến prev_time = timestamp trước đó.
4. Gặp start: nếu stack không rỗng, cộng time - prev_time cho hàm trên đỉnh stack. Push hàm mới, cập nhật prev_time = time.
5. Gặp end: pop hàm, cộng time + 1 - prev_time cho hàm đó. Cập nhật prev_time = time + 1.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

void print_vec(vector<int> v) {
    cout << "[";
    for (int x : v) cout << x << ", ";
    cout << "]" << endl;
}

class Solution {
public:
    vector<int> exclusiveTime(int n, vector<string>& logs) {
        vector<int> res(n, 0);
        stack<int> st;
        int prev = 0;
        for (auto& log : logs) {
            int id = 0, time = 0, i = 0;
            while (log[i] != ':') id = id * 10 + (log[i++] - '0');
            i++; // skip ':'
            bool isStart = (log[i] == 's');
            while (log[i] != ':') i++;
            i++;
            while (i < log.size()) time = time * 10 + (log[i++] - '0');
            if (isStart) {
                if (!st.empty()) res[st.top()] += time - prev;
                st.push(id);
                prev = time;
            } else {
                int top = st.top(); st.pop();
                res[top] += time + 1 - prev;
                prev = time + 1;
            }
        }
        return res;
    }
};

int main() {
    vector<string> v = {"0:start:0","1:start:2","1:end:5","0:end:6"};
    Solution ob;
    print_vec(ob.exclusiveTime(2, v)); // [3, 4]
    return 0;
}

Độ phức tạp

• Thời gian: O(L) (L = tổng độ dài log).
• Không gian: O(n) cho stack và kết quả.