"""
tc O(N) sc O(N)
stack store id, each time get a 'start' log, update its previous id's acuumutive time
each time get a 'end' log, pop off cached id since the job has ended; and update ended job's accumutive time
each log, cache its timestamp w previous
1. iterate each log, split format into id, type, time
2. check type if it's start or end
3. if start, before push current id into stack, get time diff since last timestamp from top stack; update previous time
4 if end, pop off top stack id, get time diff and update exclusive time, update prev time
Note, when type is start, time diff = t - prev , updated prev = t ; when type== 'end', diff = t - prev + 1 ; updated prev = t + 1
reason is because at same timestamp, end, start point has 1 unit time inteval.
"""
class Solution:
def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:
res = [0] * n
st = []
prev = None
for log in logs:
id, tp, t = log.split(':')
id = int(id)
t = int(t)
#print('before',st,res,t,prev)
if tp == 'start':
if st:
res[st[-1]] += t-prev
st.append(id)
prev = t
else:# tp == 'end'
prev_id = st.pop()
res[prev_id] += t-prev + 1
prev = t + 1
#print('after',st,res,t,prev)
return res
time penalty solution
class Solution:
def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:
res = [0] * n
st = []
prev_t = 0
for l in logs:
iD,tp,t =l.split(':')
iD = int(iD)
t = int(t)
if tp == 'start':
st.append(t)
else:
diff = t - st.pop() +1
res[iD] += diff
st = [t+diff for t in st ]
return res