Exclusive Time of Functions

Statement

We are given an integer number, n, representing the number of functions running in a single-threaded CPU, and an execution log, which is essentially a list of strings. Each string has the format {function id}:{"start" | "end"}:{timestamp}, indicating that the function with function id either started or stopped execution at the time identified by the timestamp value. Each function has a unique ID between $0$ and $n-1$. Compute the exclusive time of the functions in the program.

Note: The exclusive time is the sum of the execution times for all the calls to a specific function.

Constraints:

• $1 \leq$ n $\leq 100$
• $1 \leq$ logs.length $\leq 500$
• $0 \leq$ function id $<$ n
• $0 \leq$ timestamp $\leq 10^3$
• No two start events and two end events will happen at the same timestamp.
• Each function has an end log entry for each start log entry.

Examples

Each function is identified in the logs by a function id. Each log entry is formatted in the following way:

{function id}:{"start" | "end"}:{timestamp}

The above log entries indicate that three functions with IDs 0, 1, and 2 are executed as shown in the following figure. The function with ID 0 started execution at time 0 and ended at time 8. However, since this is a single-threaded CPU, only one function can run at a time. So, when the function with ID 1 starts execution at time 2, the function with ID 0 is preempted. As soon as the function with ID 1 stops execution at time 3, the function with ID 2 starts execution, so the function with ID 0 still remains preempted. Finally, the function with ID 2 ends execution at time 7 and the function with ID 0 resumes and finishes execution at time 8.

Our task is to return the total time for which each function ran. For example, the function with ID 0 ran for a total of 3 time units.

Here are some example inputs and the corresponding expected output:

Understand the problem

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Figure it out!

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Try it yourself

Implement your solution in main.java in the following coding playground. The supporting code template provided in Event.java is meant to assist in developing your solution to the problem.