Meesho Order Stage Exclusive Processing Time
Meesho's order fulfillment system processes orders through various stages like OrderValidation, PaymentProcessing, LogisticsAssignment, etc. Each stage has a defined start and end event, and stages can be nested (e.g., PaymentProcessing might start and end within OrderValidation). To optimize our systems, we need to accurately measure the exclusive time spent in each stage, meaning the time a stage was active and no sub-stage was running.
You are given a list of log entries, each representing a start or end event for a specific order processing stage. Your task is to calculate the total exclusive processing time for each stage ID.
start or end), and timestamp.Input:
n: number, the number of distinct stage IDs.
logs: string[], an array of log entries. Each entry is a string in the format "stage_id:event_type:timestamp".
stage_id: an integer from 0 to n-1.event_type: either "start" or "end".timestamp: a non-negative integer representing seconds.Output:
number[], an array of size n where output[i] is the total exclusive time for stage_id = i.
start events will have a corresponding end event.start events for the same stage ID without an intervening end event. This implies a valid call stack model.timestamp can be large, but n (number of stage IDs) will be relatively small.Examples
Example 1
Input:
n = 2, logs = ["0:start:0", "1:start:2", "1:end:5", "0:end:6"]
Output:
[3,3]
Note:
Stage 0 starts at t=0. Stage 1 starts at t=2, so stage 0 is paused and accumulates 2 units (0 to 2). Stage 1 runs exclusively from t=2 to t=5 (3 units). Stage 1 ends, stage 0 resumes at t=5. Stage 0 runs exclusively from t=5 to t=6 (1 unit). Total for stage 0: 2+1=3. Total for stage 1: 3.
Example 2
Input:
n = 1, logs = ["0:start:0", "0:start:1", "0:end:2", "0:end:3"]
Output:
[3]
Note:
Stage 0 starts at t=0. Another instance of Stage 0 (recursive call) starts at t=1, pausing the first. The inner Stage 0 runs from t=1 to t=2 (1 unit). The inner Stage 0 ends, the outer Stage 0 resumes at t=2. The outer Stage 0 runs from t=2 to t=3 (1 unit). The total time accumulated for stage 0 is (1-0) + (2-1) + (3-2) = 1 + 1 + 1 = 3.
Example 3
Input:
n = 3, logs = ["0:start:0", "1:start:1", "2:start:2", "2:end:3", "1:end:4", "0:end:5"]
Output:
[2,2,1]
Note:
Stage 0 runs from t=0 to t=1 (1 unit). Stage 1 runs from t=1 to t=2 (1 unit). Stage 2 runs from t=2 to t=3 (1 unit). Stage 1 resumes from t=3 to t=4 (1 unit). Stage 0 resumes from t=4 to t=5 (1 unit). Total for stage 0: 1+1=2. Total for stage 1: 1+1=2. Total for stage 2: 1.
Constraints
1 <= n <= 100 (Number of distinct stage IDs)1 <= logs.length <= 10^40 <= stage_id < n0 <= timestamp <= 10^9event_type is strictly either "start" or "end".start has a matching end, and the end event for stage_X will only occur if stage_X is currently at the top of the call stack).logs.length.Loading editor...