Approach #1 Using Stack [Time Limit Exceeded]
Before starting off with the solution, let's discuss a simple idea. Suppose we have three functions , and such that calls and then calls . In this case, starts at the end and ends first, starts at 2nd position and ends at the 2nd last step. Similarly, starts first and ends at the last position. Thus, we can conclude that the function which is entered at the end finishes first and the one which is entered first ends at the last position.
From the above discussion, we can conclude that we can make use of a to solve the given problem. We can start by pushing the first function's id from the given list onto the array. We also keep a track of the current . We also make use of a array, such that is to keep a track of the exclusive time spent by the Fucntion with function id till the current time.
Now, we can move on to the next function in . The start/end time of the next function will obviously be larger than the start time of the function on the . We keep on incrementing the current and the exclusive time for the function on the top of the till the current time becomes equal to the start/end time of the next function in the list.
Thus, now, we've reached a point, where the control shifts from the last function to a new function, due to a function call(indicated by a start label for the next function), or the last function could exit(indicated by the end label for the next function). Thus, we can no longer continue with the same old function.
If the next function includes a start label, we push this function on the top of the , since the last function would need to be revisited again in the future. On the other hand, if the next function includes an end label, it means the last function on the top of the is terminating.
We also know that an end label indicates that this function executes till the end of the given time. Thus, we need to increment the current and the exclusive time of the last function as well to account for this fact. Now, we can remove(pop) this function from the . We can continue this process for every function in the list.
At the end, the array gives the exclusive times for each function.
Summarizing the above process, we need to do the following:
Push the function id of the first function in the list on the .
Keep incrementing the exlusive time(along with the current time) corresponding to the function on the top of the (in the array), till the current time equals the start/end time corresponding to the next function in the list.
If the next function has a 'start' label, push this function's id onto the stack. Otherwise, increment the last function's exclusive time(along with the current time), and pop the function id from the top of the stack.
Repeat steps 2 and 3 till all the functions in the list have been considered.
Return the resultant exlcusive time().
Time complexity : . We increment the time till all the functions are done with the execution. Here, refers to the end time of the last function in the list.
Space complexity : . The can grow upto a depth of atmost . Here, refers to the number of elements in the given list.
Approach #2 Better Approach [Accepted]
In the last approach, for every function on the top of the , we incremented the current time and the exclusive time of this same function till the current time became equal to the start/end time of the next function.
Instead of doing this incrementing step by step, we can directly use the difference between the next function's start/stop time and the current function's start/stop time. The rest of the process remains the same as in the last approach.
The following animation illustrates the process.
Time complexity : . We iterate over the entire array just once. Here, refers to the number of elements in the list.
Space complexity : The can grow upto a depth of atmost . Here, refers to the number of elements in the given list.
Analysis written by: @vinod23