Reschedule Meetings for Maximum Free Time I - Solution & Explanation

Problem Overview: You are given a schedule of non‑overlapping meetings inside a fixed event duration. You may reschedule up to k meetings while keeping their durations the same. The goal is to maximize the length of a single continuous block of free time.

Approach 1: Sliding Window on Meetings (O(n) time, O(n) space)

The key observation: if you move k meetings elsewhere, the gap created spans from the end of the meeting before the window to the start of the meeting after the window. Iterate through the meetings and consider every group of k consecutive meetings as candidates to reschedule. For a window starting at i, the left boundary is the end time of meeting i-1 (or 0 if it’s the first meeting). The right boundary is the start time of meeting i+k (or eventTime if the window reaches the end). The free time becomes rightStart - leftEnd. A sliding window efficiently checks all such groups in linear time.

This works because removing a contiguous block of meetings merges the surrounding gaps into one large free interval. The approach naturally fits problems involving ordered intervals and window scanning, which often appear with array processing.

Approach 2: Sliding Window with Space Optimization (O(n) time, O(1) space)

You can compute the same window boundaries without storing extra structures. Track indices directly and compute boundaries using the original startTime and endTime arrays. For each index i, determine the previous meeting’s end and the next meeting’s start using simple conditional checks. The maximum difference across all windows is the answer.

This version reduces memory usage while preserving the same logic. The algorithm remains linear because each meeting index is visited once and each window shift performs constant work. The method also reflects a typical greedy perspective: remove the block of meetings that unlocks the largest possible continuous gap.

Recommended for interviews: The sliding window solution is what interviewers expect. It shows you recognize that removing k consecutive meetings merges surrounding gaps and can be evaluated with a linear scan. A brute‑force approach that tries all combinations would be exponential or O(n^2), which demonstrates baseline reasoning but not the optimization skills usually required for medium interval problems.