Exclusive Time of Functions
Stack of currently-running functions; on each log line, charge elapsed time to the stack top.
Problem#
Given function-call logs of the form "id:start:t" or "id:end:t" on a single thread, return each function’s exclusive run time.
Examples#
n = 2, logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]→[3,4]n = 1, logs = ["0:start:0","0:start:2","0:end:5","0:start:6","0:end:6","0:end:7"]→[8]
Constraints#
1 <= n <= 100,1 <= logs.length <= 500.
Approach#
Stack stores currently-running function ids. Maintain prev = the timestamp of the last event. On any log line, charge (t - prev) to the function currently on top. On start, push the new function. On end, pop and advance prev = t + 1 (the function ran through the end of that tick); otherwise prev = t.
Solution#
class Solution {public: vector<int> exclusiveTime(int n, vector<string>& logs) { vector<int> ans(n, 0); stack<int> st; int prev = 0; for (auto& line : logs) { int p1 = line.find(':'), p2 = line.find(':', p1 + 1); int id = stoi(line.substr(0, p1)); string ev = line.substr(p1 + 1, p2 - p1 - 1); int t = stoi(line.substr(p2 + 1)); if (ev == "start") { if (!st.empty()) ans[st.top()] += t - prev; st.push(id); prev = t; } else { ans[st.top()] += t - prev + 1; st.pop(); prev = t + 1; } } return ans; }};import ( "strconv" "strings")
func exclusiveTime(n int, logs []string) []int { ans := make([]int, n) st := []int{} prev := 0 for _, line := range logs { parts := strings.Split(line, ":") id, _ := strconv.Atoi(parts[0]) ev := parts[1] t, _ := strconv.Atoi(parts[2]) if ev == "start" { if len(st) > 0 { ans[st[len(st)-1]] += t - prev } st = append(st, id) prev = t } else { ans[st[len(st)-1]] += t - prev + 1 st = st[:len(st)-1] prev = t + 1 } } return ans}from typing import List
class Solution: def exclusiveTime(self, n: int, logs: List[str]) -> List[int]: ans = [0] * n st = [] prev = 0 for line in logs: id_s, ev, t_s = line.split(':') fid = int(id_s) t = int(t_s) if ev == "start": if st: ans[st[-1]] += t - prev st.append(fid) prev = t else: ans[st[-1]] += t - prev + 1 st.pop() prev = t + 1 return ansfunction exclusiveTime(n, logs) { const ans = new Array(n).fill(0); const st = []; let prev = 0; for (const line of logs) { const [idStr, ev, tStr] = line.split(':'); const id = parseInt(idStr, 10); const t = parseInt(tStr, 10); if (ev === 'start') { if (st.length > 0) ans[st[st.length - 1]] += t - prev; st.push(id); prev = t; } else { ans[st[st.length - 1]] += t - prev + 1; st.pop(); prev = t + 1; } } return ans;}class Solution { public int[] exclusiveTime(int n, List<String> logs) { int[] ans = new int[n]; Deque<Integer> st = new ArrayDeque<>(); int prev = 0; for (String line : logs) { String[] parts = line.split(":"); int id = Integer.parseInt(parts[0]); String ev = parts[1]; int t = Integer.parseInt(parts[2]); if (ev.equals("start")) { if (!st.isEmpty()) ans[st.peek()] += t - prev; st.push(id); prev = t; } else { ans[st.peek()] += t - prev + 1; st.pop(); prev = t + 1; } } return ans; }}function exclusiveTime(n: number, logs: string[]): number[] { const ans = new Array<number>(n).fill(0); const st: number[] = []; let prev = 0; for (const line of logs) { const [idStr, ev, tStr] = line.split(':'); const id = parseInt(idStr, 10); const t = parseInt(tStr, 10); if (ev === 'start') { if (st.length > 0) ans[st[st.length - 1]] += t - prev; st.push(id); prev = t; } else { ans[st[st.length - 1]] += t - prev + 1; st.pop(); prev = t + 1; } } return ans;}Editorial#
Time is one-dimensional: between consecutive events, the function on the stack top “owns” the CPU. The +1 on end is because both start and end happen at the beginning of their tick — so an end at time t includes tick t itself.
Complexity#
- Time: O(L) where L is total log length.
- Space: O(n).
Concept revision#
Related#