Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Moving a consecutive group of meetings while preserving their order lets their surrounding free gaps merge. Pack those meetings against one side of the interval bounded by the unchanged neighbors. The remaining uninterrupted free time equals that interval's length minus the group's total duration.

Approach

Build prefix sums of meeting durations. Enumerate every block of k consecutive meetings. Its left boundary is the previous meeting's end, or zero; its right boundary is the following meeting's start, or eventTime. Use the prefix sums to subtract the block's total duration from that available interval and maximize the result.

This is the sum of the block's k + 1 adjacent free gaps. Any free interval created by moving at most k meetings can merge only such a consecutive group of gaps. Since gap lengths are nonnegative, a shorter group can be extended to a full k-meeting block without worsening its candidate value. Thus the enumeration also covers using fewer moves.

class Solution:
    def maxFreeTime(self, eventTime: int, k: int, startTime: List[int], endTime: List[int]) -> int:
        n = len(startTime)
        res = 0
        pre = [endTime[0] - startTime[0]]

        for i in range(1, n):
            pre.append(pre[-1] + endTime[i] - startTime[i])

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

        return res

Complexity analysis

Let n be the number of meetings. Time: O(n). Auxiliary space: O(n) for cumulative meeting durations.