When multiple tasks are executed on a single-threaded CPU, the tasks are scheduled based on the principle of pre-emption. When a higher-priority task arrives in the execution queue, then the lower-priority task is pre-empted, i.e. its execution is paused until the higher-priority task is complete.
There are n functions to be executed on a single-threaded CPU, with each function having a unique ID between 0 and n - 1. Given an integer n representing the number of functions to be executed, and an execution log, as an array of strings, logs, of size m, determine the exclusive times of each of the functions. Exclusive time is the sum of execution times for all calls to a function. Any string representing an execution log is of the form {function_id}:{start/end}:{timestamp}, indicating that the function with ID = function_id, either starts or ends at a time identified by the timestamp value.
Note: While calculating the execution time of a function call, both the starting and ending times of the function call have to be included. The log of the form {function_id}:{start}:{timestamp} means that the running function is preempted at the beginning of timestamp timestamp. The log of the form {function_id}:{end}:{timestamp} means that the function function_id is preempted after completing its execution at timestamp second i.e. after timestamp second.
Function Description
Complete the function getTotalExecutionTime in the editor below.
getTotalExecutionTime has the following parameters:
- 1.
int n: the number of functions to be executed - 2.
string logs[m]: the execution logs of the different calls to the functions
Returns
int[n]: the execution time of all functions with IDs from 0 to n - 1.
Example 1:
Input: n = 2, logs = ["0:start:0", "1:start:3", "1:end:6", "0:end:10"]
Output: [7, 4]
Explanation:The execution of functions happens in the following order:
Thus the exclusive times for different functions are as follows:
- Time = [0, 3]: Function ID = 0 executes
- Time = [3, 6]: Function ID = 1 executes
- Time = [6, 10]: Function ID = 0 executes
- Function (ID = 0) = 3 + 4 = 7
- Function (ID = 1) = 3 = 4
Example 2:
Input: n = 3, logs = ["0:start:0", "1:start:3", "1:end:6", "2:start:8", "2:end:10", "0:end:12"]
Output: [6, 4, 3]
Explanation:The execution of functions happens in the following order:
Thus the exclusive times for different functions are as follows:
- Time = [0, 3]: Function ID = 0 executes
- Time = [3, 6]: Function ID = 1 executes
- Time = [6, 8]: Function ID = 0 executes
- Time = [8, 10]: Function ID = 2 executes
- Time = [11, 12]: Function ID = 0 executes
So the answer to be returned is [6, 4, 3].
- Function (ID = 0) = 3 + 1 + 2 = 6
- Function (ID = 1) = 4 = 4
- Function (ID = 2) = 3
1 ≤ n ≤ 1001 ≤ m ≤ 5000 ≤ function_id < n0 ≤ timestamp ≤ 10^3- The timestamps are given in non-decreasing order.
- No two starting timestamps and no two ending timestamps are equal.
- Every function "start" call has a corresponding function "end" call.
input:
output: