initial
so hard like even now i dont 100% get it. I thought of making initial size gap list and doing on it but the implement and calculation of gaps whenever current event is removed I can think of it
if we use prefix and suffix where
pre[i] = maximum gap among meetings [0, i-1] (gaps before meeting i)
So:
pre[0] = max gap before meeting 0 = 0 (no meetings before)
pre[1] = max gap before meeting 1 = max gap in range [0,0] = gap before meeting 0
pre[2] = max gap before meeting 2 = max gap in range [0,1] = max(gap before M0, gap before M1)
pre[3] = max gap before meeting 3 = max gap in range [0,2] = max(gap before M0, M1, M2)
and similarly for suffix, it shows the maximum gaps that are before the current meeting and after the current meeting. So for current event, when we remove it we first can calculate
1) the gap caused by removing this cur event, which is startTime[i+1]-endTime[i-1]
2) whether this gap can fit in either pre[i] or suff[i+1] (i+1 and not i cuz suff[i] is largest gap after i (includes the gap immediately after meeting i, which gets merged into the created gap when we remove meeting i) but suff[i+1] excludes the gap to the right of current_meeting[i]
2.1) if we can fit this gap, there is a valid position so we can update answer with this gap
2.2) else, we cant fit so we have to gap-current_meeting_duration and update that to ans
class Solution:
def maxFreeTime(self, eventTime: int, startTime: List[int], endTime: List[int]) -> int:
n=len(startTime)
suff=[0 for _ in range(n+1)]
pre=[0 for _ in range(n+1)]
ans=startTime[0]
prev=0
end=eventTime
for i in range(n):
gap = startTime[i]-prev
ans=max(gap,ans)
prev = endTime[i]
pre[i+1]=max(pre[i],gap)
ans=max(ans,eventTime-endTime[-1])
for i in range(n-1,-1,-1):
gap = end - endTime[i]
end=startTime[i]
suff[i]=max(suff[i+1],gap)
for i in range(n):
if i==0:
prev=0
else:
prev=endTime[i-1]
if i==n-1:
end=eventTime
else:
end=startTime[i+1]
gap = end-prev
meeting_duration=endTime[i]-startTime[i]
if pre[i]>=meeting_duration or suff[i+1]>=meeting_duration:
ans=max(ans,gap)
else:
ans=max(ans,gap-meeting_duration)
return ans
complexity
n time and space
