A profiler on a single-core machine writes one log line whenever a task gets or gives up the CPU. Each line is a list of three strings [task, action, timestamp]:
actionis"enter"(the task starts running) or"exit"(the task finishes).timestampis a non-negative integer written as a decimal string, e.g."42".
Tasks nest: when a task enters while another one is running, the running task is suspended until the new one exits, and then it resumes. Only the innermost running task uses the CPU. The same task name can appear many times, including nested inside itself (recursion).
Time is continuous: a task that enters at t1 and exits at t2 with nothing nested inside it uses t2 - t1 units. A task that enters and exits at the same timestamp uses 0.
Implement:
def cpu_usage(logs: list[list[str]]) -> dict[str, int]
Return, for every task name that appears in the logs, its total exclusive CPU time (time it was the innermost running task), summed over all of its runs. Names that never got any time map to 0.
The log lines are not in order. Sort them by timestamp as integers. Lines with equal timestamps keep their relative order from the input (a stable sort). After that ordering, the log is guaranteed well-formed: every exit closes the most recent still-open enter of the same task, and every enter is eventually closed. logs may be empty.
cpu_usage([
["render", "enter", "0"],
["fetch", "enter", "2"],
["fetch", "exit", "7"],
["render", "exit", "10"],
])
# {"render": 5, "fetch": 5} render runs 0-2 and 7-10, fetch runs 2-7
cpu_usage([
["b", "exit", "9"],
["a", "enter", "1"],
["b", "enter", "3"],
["a", "exit", "12"],
])
# {"a": 5, "b": 6} sorted: a enters 1, b enters 3, b exits 9, a exits 12
Constraints: up to 200,000 log lines, nesting can be as deep as half of that, timestamps up to 10^12. Aim for O(n log n) overall; the ordering is the only log factor.
Show hint
between two consecutive events, only one task can have been using the CPU: the innermost one still running.