เวลาการทำงานเฉพาะของฟังก์ชันใน C++

CPU single-threaded รันฟังก์ชันหลายตัว มี log แบบ "function_id:start|end:timestamp" ต้องการหา exclusive time ของแต่ละฟังก์ชัน (เวลาที่รันจริง ไม่นับเวลาที่ยield ให้ฟังก์ชันอื่น)

ตัวอย่าง: n=2, logs=["0:start:0","1:start:2","1:end:5","0:end:6"] → [3,4]

ขั้นตอนการแก้ปัญหา (Stack)

1. อาร์เรย์ ret[n] เก็บเวลา, สแต็ก st เก็บ function_id
2. prev = 0 (timestamp ก่อนหน้า)
3. วนแต่ละ log:
   • แยก id, type, timestamp
   • ถ้า start:
     • ถ้า stack ไม่ว่าง → เพิ่ม timestamp - prev ให้ฟังก์ชันบนสุด
     • push id, prev = timestamp
   • ถ้า end:
     • pop x ออก, เพิ่ม (timestamp + 1) - prev ให้ x
     • prev = timestamp + 1
4. คืน ret

ตัวอย่างโค้ด C++

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

void print_vector(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> ret(n);
        stack<int> st;
        int prev = 0;
        for (string& log : logs) {
            int id = 0, timestamp = 0, j = 0;
            while (log[j] != ':') { id = id*10 + (log[j]-'0'); j++; }
            j++;
            string type = "";
            while (log[j] != ':') { type += log[j]; j++; }
            j++;
            while (j < log.size()) { timestamp = timestamp*10 + (log[j]-'0'); j++; }
            if (type == "start") {
                if (!st.empty()) ret[st.top()] += timestamp - prev;
                st.push(id);
                prev = timestamp;
            } else {
                int x = st.top(); st.pop();
                ret[x] += (timestamp + 1) - prev;
                prev = timestamp + 1;
            }
        }
        return ret;
    }
};

int main() {
    vector<string> v = {"0:start:0","1:start:2","1:end:5","0:end:6"};
    Solution ob;
    print_vector(ob.exclusiveTime(2, v));
}

Input

2 ["0:start:0","1:start:2","1:end:5","0:end:6"]

Output

[3, 4, ]