Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Removing one meeting joins its two neighboring gaps with its occupied time. If the meeting fits in a different, nonadjacent gap, that whole interval becomes free. Otherwise it must remain inside that interval, and only the sum of its neighboring gaps can become uninterrupted.

Approach

Mark which meetings can be relocated elsewhere. Scan left to right while tracking the largest earlier nonadjacent gap, and compare it with each meeting's duration before adding that meeting's immediately preceding gap. Repeat right to left for later gaps, again comparing before incorporating the adjacent gap. This update order excludes the two gaps that belong to the interval being freed.

For each meeting, find the span between the previous meeting's end and the next meeting's start, using event boundaries where necessary. If relocation is possible, the entire span is a candidate. Otherwise subtract the meeting's duration, corresponding to sliding it against either end. Return the largest candidate. This also includes schedules requiring no useful move.

class Solution:
    def maxFreeTime(self, eventTime: int, startTime: List[int], endTime: List[int]) -> int:
        n = len(startTime)
        available_space = [False] * n
        s1 = 0

        for i in range(n):
            if endTime[i] - startTime[i] <= s1:
                available_space[i] = True
            s1 = max(s1, startTime[i] - (0 if i == 0 else endTime[i - 1]))

        s2 = 0
        for i in range(n - 1, -1, -1):
            if endTime[i] - startTime[i] <= s2:
                available_space[i] = True
            s2 = max(s2, (eventTime if i == n - 1 else startTime[i + 1]) - endTime[i])

        res = 0
        for i in range(n):
            left = 0 if i == 0 else endTime[i - 1]
            right = eventTime if i == n - 1 else startTime[i + 1]
            if available_space[i]:
                res = max(res, right - left)
            else:
                res = max(res, right - left - (endTime[i] - startTime[i]))

        return res

Complexity analysis

Let n be the number of meetings. Time: O(n). Auxiliary space: O(n) for relocation-availability flags.