If a meeting can be shifted into a non-adjacent free slot (not touching its immediate neighbors), it can create a new free interval equal to the sum of its own duration and the two adjacent free intervals.
Otherwise, moving the meeting merges the two adjacent free intervals into one, minus the duration of the meeting itself.

By precomputing which meetings can be shifted into such slots, we can efficiently determine the maximum possible free interval after moving any meeting.

Approach

For each meeting, check if it can be moved into a non-adjacent free slot on the left or right by traversing from both directions and recording the maximum non-adjacent free slot seen so far.
For each meeting, calculate the left and right boundaries (end of previous meeting and start of next meeting).
If the meeting can be moved into a non-adjacent slot, the new free interval is right - left.
Otherwise, the new free interval is right - left - (endTime[i] - startTime[i]).
Return the maximum value found.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int maxFreeTime(int eventTime, vector<int>& s, vector<int>& e) {\n        int n = s.size();\n        vector<bool> q(n, false);\n        for(int i=0, t1=0, t2=0; i<n; ++i) {\n            if(e[i]-s[i]<=t1) q[i]=true;\n            t1 = max(t1, s[i]-(i==0?0:e[i-1]));\n            if(e[n-i-1]-s[n-i-1]<=t2) q[n-i-1]=true;\n            t2 = max(t2, (i==0?eventTime:s[n-i])-e[n-i-1]);\n        }\n        int ans=0;\n        for(int i=0;i<n;++i) {\n            int left = i==0?0:e[i-1];\n            int right = i==n-1?eventTime:s[i+1];\n            if(q[i]) ans = max(ans, right-left);\n            else ans = max(ans, right-left-(e[i]-s[i]));\n        }\n        return ans;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    int</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> maxFreeTime</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> eventTime</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">></span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x26;</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> s</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span sty

Related Tags

Continue Practicing