{ "cells": [ { "cell_type": "markdown", "source": [ "On a **single-threaded** CPU, we execute a program containing `n` functions.\n", "Each function has a unique ID between `0` and `n-1`.\n", "\n", "Function calls are **stored in a[call\n", "stack](https://en.wikipedia.org/wiki/Call_stack)**: when a function call\n", "starts, its ID is pushed onto the stack, and when a function call ends, its ID\n", "is popped off the stack. The function whose ID is at the top of the stack is\n", "**the current function being executed**. Each time a function starts or ends,\n", "we write a log with the ID, whether it started or ended, and the timestamp.\n", "\n", "You are given a list `logs`, where `logs[i]` represents the `ith` log message\n", "formatted as a string `\"{function_id}:{\"start\" | \"end\"}:{timestamp}\"`. For\n", "example, `\"0:start:3\"` means a function call with function ID `0` **started at\n", "the beginning** of timestamp `3`, and `\"1:end:2\"` means a function call with\n", "function ID `1` **ended at the end** of timestamp `2`. Note that a function\n", "can be called **multiple times, possibly recursively**.\n", "\n", "A function's **exclusive time** is the sum of execution times for all function\n", "calls in the program. For example, if a function is called twice, one call\n", "executing for `2` time units and another call executing for `1` time unit, the\n", "**exclusive time** is `2 + 1 = 3`.\n", "\n", "Return _the **exclusive time** of each function in an array, where the value\n", "at the _`ith` _index represents the exclusive time for the function with\n", "ID_`i`.\n", "\n", "\n", "\n", "**Example 1:**\n", "\n", "![](https://assets.leetcode.com/uploads/2019/04/05/diag1b.png)\n", "\n", "\n", "\n", " Input: n = 2, logs = [\"0:start:0\",\"1:start:2\",\"1:end:5\",\"0:end:6\"]\n", " Output: [3,4]\n", " Explanation:\n", " Function 0 starts at the beginning of time 0, then it executes 2 for units of time and reaches the end of time 1.\n", " Function 1 starts at the beginning of time 2, executes for 4 units of time, and ends at the end of time 5.\n", " Function 0 resumes execution at the beginning of time 6 and executes for 1 unit of time.\n", " So function 0 spends 2 + 1 = 3 units of total time executing, and function 1 spends 4 units of total time executing.\n", "\n", "\n", "**Example 2:**\n", "\n", "\n", "\n", " Input: n = 1, logs = [\"0:start:0\",\"0:start:2\",\"0:end:5\",\"0:start:6\",\"0:end:6\",\"0:end:7\"]\n", " Output: [8]\n", " Explanation:\n", " Function 0 starts at the beginning of time 0, executes for 2 units of time, and recursively calls itself.\n", " Function 0 (recursive call) starts at the beginning of time 2 and executes for 4 units of time.\n", " Function 0 (initial call) resumes execution then immediately calls itself again.\n", " Function 0 (2nd recursive call) starts at the beginning of time 6 and executes for 1 unit of time.\n", " Function 0 (initial call) resumes execution at the beginning of time 7 and executes for 1 unit of time.\n", " So function 0 spends 2 + 4 + 1 + 1 = 8 units of total time executing.\n", "\n", "\n", "**Example 3:**\n", "\n", "\n", "\n", " Input: n = 2, logs = [\"0:start:0\",\"0:start:2\",\"0:end:5\",\"1:start:6\",\"1:end:6\",\"0:end:7\"]\n", " Output: [7,1]\n", " Explanation:\n", " Function 0 starts at the beginning of time 0, executes for 2 units of time, and recursively calls itself.\n", " Function 0 (recursive call) starts at the beginning of time 2 and executes for 4 units of time.\n", " Function 0 (initial call) resumes execution then immediately calls function 1.\n", " Function 1 starts at the beginning of time 6, executes 1 units of time, and ends at the end of time 6.\n", " Function 0 resumes execution at the beginning of time 6 and executes for 2 units of time.\n", " So function 0 spends 2 + 4 + 1 = 7 units of total time executing, and function 1 spends 1 unit of total time executing.\n", "\n", "\n", "**Example 4:**\n", "\n", "\n", "\n", " Input: n = 2, logs = [\"0:start:0\",\"0:start:2\",\"0:end:5\",\"1:start:7\",\"1:end:7\",\"0:end:8\"]\n", " Output: [8,1]\n", "\n", "\n", "**Example 5:**\n", "\n", "\n", "\n", " Input: n = 1, logs = [\"0:start:0\",\"0:end:0\"]\n", " Output: [1]\n", "\n", "\n", "\n", "\n", "**Constraints:**\n", "\n", " * `1 <= n <= 100`\n", " * `1 <= logs.length <= 500`\n", " * `0 <= function_id < n`\n", " * `0 <= timestamp <= 109`\n", " * No two start events will happen at the same timestamp.\n", " * No two end events will happen at the same timestamp.\n", " * Each function has an `\"end\"` log for each `\"start\"` log." ], "metadata": {} }, { "outputs": [ { "output_type": "execute_result", "data": { "text/plain": "exclusive_time (generic function with 1 method)" }, "metadata": {}, "execution_count": 1 } ], "cell_type": "code", "source": [ "# @lc code=start\n", "using LeetCode\n", "\n", "function exclusive_time(n::Int, logs::Vector{T}) where {T<:AbstractString}\n", " logs = [\n", " (parse(Int, id) + 1, state, parse(Int, time)) for\n", " (id, state, time) in split.(logs, ':')\n", " ]\n", " task, _, pretime = first(logs)\n", " times, tasks = zeros(Int, n), [task]\n", " for (id, state, curtime) in @views(logs[2:end])\n", " interval, pretime = curtime - pretime, curtime\n", " isempty(tasks) || (times[last(tasks)] += interval)\n", " if state == \"start\" ## new task started\n", " push!(tasks, id)\n", " else ## task ended\n", " times[pop!(tasks)] += 1 ## add end time\n", " pretime += 1\n", " end\n", " end\n", " return times\n", "end\n", "# @lc code=end" ], "metadata": {}, "execution_count": 1 }, { "cell_type": "markdown", "source": [ "---\n", "\n", "*This notebook was generated using [Literate.jl](https://github.com/fredrikekre/Literate.jl).*" ], "metadata": {} } ], "nbformat_minor": 3, "metadata": { "language_info": { "file_extension": ".jl", "mimetype": "application/julia", "name": "julia", "version": "1.10.1" }, "kernelspec": { "name": "julia-1.10", "display_name": "Julia 1.10.1", "language": "julia" } }, "nbformat": 4 }